fill2714 is known to be very good at dice games. However, the reason he is good at dice games is that he can actually manipulate the dice to produce any number he wants.

The rules of the dice game are as follows:

• The game board consists of infinitely many squares arranged in a row, numbered with non-negative integers starting from the starting square, $0$.
• There are $K$ "deserted island" squares on the board, where the $i$-th deserted island square is at position $x_i$.
• All players place their pieces on square $0$.
• When it is a player's turn, the player performs the following process:
  1. Roll two dice, each with numbers from $1$ to $N$, and move the piece forward by the sum of the two numbers.
  2. If the two numbers rolled in step 1 are the same, perform a double action.
  3. If the condition in step 2 is not met, end the turn.
  4. Repeat steps 1, 2, and 3 until the turn ends.
• The double action is as follows:
  1. If this is the $M$-th double action, move to square $0$ and end the turn.
  2. If the condition in step 1 is not met and the current square is a deserted island, end the turn.
  3. If neither condition 1 nor 2 is met, continue the turn.

fill2714 has decided to manipulate the dice again to move as far as possible in his first turn. Find the maximum square number fill2714 can reach and end his turn on during his first turn.

Input

The first line contains the maximum value $N$ that can appear on a die, the double limit $M$, and the number of deserted island squares $K$, separated by spaces. $(1 \le N \le 10^{12}; 1 \le M \le 10^5; 0 \le K \le 10^5)$

The second line contains $x_{1}, x_{2}, \ldots, x_{K}$ separated by spaces.

$(1 \le x_{i} \le 10^{18}; x_{i} < x_{i+1})$

Output

Output the maximum square number fill2714 can reach and end his turn on during his first turn.

Examples

Input 1

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

Output 1

27