fill2714는 주사위 게임을 매우 잘하는 것으로 알려져 있다. 하지만 그가 주사위 게임을 잘 하는 이유는 사실 fill2714가 주사위를 조종하여 원하는 수가 나오게 할 수 있기 때문이다.

주사위 게임의 규칙은 다음과 같다.

• 게임판은 무한히 많은 칸이 일렬로 나열된 모양이며, 시작점인 $0$번 칸부터 차례로 음이 아닌 정수의 번호가 매겨져 있다.
• 게임판에는 $K$개의 무인도 칸이 있으며, $i$번째 무인도 칸은 $x_i$번 칸이다.
• 모든 플레이어는 $0$번 칸에 자신의 말을 놓는다.
• 플레이어의 턴이 되면 해당 플레이어가 다음 과정을 수행한다.
  1. $1$부터 $N$까지의 수가 적힌 주사위 두 개를 굴려 나온 두 수의 합만큼 말을 이동한다.
  2. 만약 $1$의 과정에서 나온 두 수가 같다면 더블 행동을 수행한다.
  3. $2$의 조건에 해당하지 않는다면 턴을 종료한다.
  4. 턴이 종료되기 전까지 $1$, $2$, $3$를 반복한다.
• 더블 행동은 다음과 같다.
  1. 지금이 $M$번째 더블 행동이라면 $0$번 칸으로 이동하고 턴을 종료한다.
  2. $1$의 조건에 해당하지 않고 현재 칸이 무인도라면 턴을 종료한다.
  3. $1$, $2$조건에 해당하지 않는다면 턴을 계속 진행한다.

fill2714는 이번에도 주사위를 조종해서 첫 턴에 최대한 많은 칸을 이동하기로 했다. fill2714가 첫 턴에 최대 몇 번 칸까지 이동한 뒤 턴을 끝낼 수 있는지 구하시오.

Input

첫 번째 줄에 주사위에서 나올 수 있는 최댓값 $N$, 더블 횟수 제한 $M$, 무인도 칸의 수 $K$가 공백으로 구분되어 주어진다. $(1 \le N \le 10^{12}; 1 \le M \le 10^5; 0 \le K \le 10^5)$

두 번째 줄에 $x_{1}, x_{2}, \ldots, x_{K}$ 가 공백으로 구분되어 주어진다. $(1 \le x_{i} \le 10^{18}; x_{i} < x_{i+1})$

Output

첫 번째 줄에 fill2714가 첫 턴에 최대 몇 번 칸까지 이동한 뒤 턴을 끝낼 수 있는지 출력한다.

Examples

Input 1

6 3 10
1 2 6 8 10 12 22 26 28 30

Output 1

27