この問題の解説はこちら。

問題文

※きたむーとはこの問題の作問のお手伝いをした人の名前である。また、きたむーの彼女はいろはちゃんではない。

きたむーは高校の競技プログラミング部に所属し、放課後も熱心にプログラミングに取り組んでいた。しかし最近、きたむーには彼女ができたようだ。

デートがしたい！　デートがしたい！　デートがしたい！

デートに着実に蝕まれていくプログラミング学習の時間。このままではきたむーのレートが落ちてしまうことに危機感を覚えたあなたは、彼の放課後のスケジュールを管理してあげることにした。

あなたは以下の点に配慮して明日以降の $N$ 日分のスケジュールを立てることにした。

• きたむーそれぞれの日の放課後に「デート」「競プロ」のうちいずれか片方の行動をとる。
• きたむーは $A$ 日以上デートできないと、愛が足りずに動けなくなってしまうので、 $A$ 日に一度は必ずデートする。
• このカップルには明日から $N$ 日以内に $B$ 回の記念日があり、それぞれ $D_1,D_2,\\cdots,D_B$ 日後である。この日には必ずデートを行う。 $D_i$ は互いに異なる。 なお、きたむーは今日デートしており、彼の高校に休日はないものとする。

あなたはきたむーが競プロに取り組む日数を最大化したい。

制約

• 入力される値はすべて整数である
• $1 \\leq N \\leq 10^{18}$
• $1 \\leq A \\leq N$
• $0 \\leq B \\leq min(N,2 \\times 10^5)$
• $1 \\leq D_i \\leq N$ $(1 \\leq i \\leq B)$
• $D_i \\neq D_j$ $(1 \\leq i,j \\leq B$ かつ $i \\neq j)$
• 入力はすべて整数

---

入力

入力は以下の形式で標準入力から与えられる。

$N$ $A$ $B$ $D_1$ $D_2$ $\\cdots$ $D_B$

出力

きたむーにプログラミング学習をさせることができる日数の最大値を$1$行で出力せよ。

---

入力例 1

10 4 2
4 6

出力例 1

7

明日から$10$日間のスケジュールを考えるが、$4$日以上競プロが連続してはならず、$4$日後、$6$日後の$2$日の記念日がある。競プロをP、デートをDと表記するなら、例えば、PPPDPDPPPDとスケジュールを組むことで$7$日競プロに取り組ませることができる。

---

入力例 2

10 1 0

出力例 2

0

寂しがりすぎ。

---

入力例 3

5 2 5
1 2 3 4 5

出力例 3

0

記念日多すぎ。

---

入力例 4

10 5 3
4 3 7

出力例 4

7

---

入力例 5

100 16 11
90 98 88 82 40 16 32 45 87 67 48

出力例 5

88