Известно, что fill2714 очень хорошо играет в кости. Однако причина его успеха заключается в том, что на самом деле fill2714 умеет управлять костями так, чтобы выпадали нужные ему числа.

Правила игры в кости следующие:

• Игровое поле представляет собой бесконечную последовательность клеток, пронумерованных неотрицательными целыми числами, начиная с начальной клетки $0$.
• На поле есть $K$ клеток «необитаемых островов», $i$-й из которых находится в клетке $x_i$.
• Все игроки начинают с фишкой на клетке $0$.
• В свой ход игрок выполняет следующие действия:
  1. Бросает две кости с числами от $1$ до $N$ и перемещает фишку на сумму выпавших чисел.
  2. Если выпавшие на двух костях числа равны, выполняется действие дубль.
  3. Если условие $2$ не выполняется, ход завершается.
  4. Действия $1$, $2$ и $3$ повторяются до тех пор, пока ход не будет завершен.
• Действие дубль заключается в следующем:
  1. Если это $M$-й по счету дубль за ход, фишка перемещается в клетку $0$ и ход завершается.
  2. Если условие $1$ не выполняется и текущая клетка является «необитаемым островом», ход завершается.
  3. Если условия $1$ и $2$ не выполняются, ход продолжается.

fill2714 решил снова воспользоваться своим умением управлять костями, чтобы за первый ход переместиться как можно дальше. Определите, в какой максимальной по номеру клетке может оказаться фишка fill2714 после завершения первого хода.

Входные данные

В первой строке через пробел заданы максимальное значение на кости $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})$

Выходные данные

В первой строке выведите максимальный номер клетки, в которой может оказаться fill2714 после завершения первого хода.

Примеры

Входные данные 1

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

Выходные данные 1

27