奶牛们想提高运动能力，因此 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