乳牛們想提高運動能力，因此 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，她才能再次開始跑步；此時可以選擇跑步或休息。

在 $N$ 分鐘鍛鍊結束時，Bessie 的疲勞係數必須恰好為 0，否則當天餘下時間的精力不足。

求 Bessie 可以跑的最大距離。

輸入格式

從標準輸入讀取輸入。

• 第 1 行：兩個空格分隔的整數 $N$ 和 $M$。
• 第 $2..N+1$ 行：第 $i+1$ 行包含單個整數 $D_i$。

輸出格式

將輸出寫入標準輸出。

• 第 1 行：一個整數，表示滿足所有條件時 Bessie 可以跑的最大距離。

範例

輸入格式 1

5 2
5
3
4
2
10

輸出格式 1

9

說明

Bessie 第一分跑步（$distance=5$），第二分休息，第三分跑步（$distance=4$），第四、第五分休息。注意第五分不能跑，否則結束時疲勞係數無法為 0。

題目作者：Neal Wu，2007