fill2714はダイスゲームが非常に得意なことで知られている。 しかし、彼がダイスゲームに強い理由は、実はfill2714がダイスを操作して望みの目を出せるからである。

ダイスゲームのルールは以下の通りである。

• ゲーム盤は無限に続くマスが一直線に並んだ形をしており、開始地点である $0$ 番のマスから順に非負整数の番号が振られている。
• ゲーム盤には $K$ 個の無人島マスがあり、$i$ 番目の無人島マスは $x_i$ 番のマスである。
• すべてのプレイヤーは $0$ 番のマスに自分の駒を置く。
• プレイヤーのターンになると、そのプレイヤーは以下の手順を行う。
  1. $1$ から $N$ までの数が書かれたダイスを2つ振り、出た2つの数の合計分だけ駒を進める。
  2. もし $1$ の手順で出た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)$

2行目に $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