E - 放課後 Editorial /

Time Limit: 1 sec / Memory Limit: 256 MB

配点: 300 点

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

問題文

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

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

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

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

あなたは以下の点に配慮して明日以降の 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