牛たちは運動能力を高めようとしており、Bessie はトラックでちょうど $N$ $(1 \le N \le 10,000)$ 分間運動します。各分、丸一分走るか休むかを選びます。

最終的な走行距離は初期値 0 の「疲労係数」に依存します。第 $i$ 分に走ると距離はちょうど $D_i$ $(1 \le D_i \le 1,000)$、係数は 1 増えますが、常に $M$ $(1 \le M \le 500)$ 以下でなければなりません。休むと一分ごとに 1 減ります。係数が 0 になるまで走り直せません。0 になれば走るか休むか選べます。

$N$ 分の運動終了時、Bessie の疲労係数はちょうど 0 でなければ、その日の残りに十分な体力が残りません。

走れる最大距離を求めてください。

入力

標準入力から読み込みます。

• 1 行目：空白区切りの整数 $N$ と $M$。
• $2..N+1$ 行目：第 $i+1$ 行には整数 $D_i$ 一つ。

出力

標準出力に書き込みます。

• 1 行目：条件を満たして走れる最大距離を表す整数一つ。

入出力例

入力 1

5 2
5
3
4
2
10

出力 1

9

注記

最初の分に走り（$distance=5$）、次は休み、3 分目に走り（$distance=4$）、4、5 分目は休みます。5 分目に走ると最後の疲労係数が 0 にならないので走れません。

問題作成者：Neal Wu、2007