测试数据来自 system/2224

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　为强健自己的体魄，小H选择的运动方式是每天进行 \(N\) 分钟的晨跑。在每分钟的开始，小H会选择下一分钟是用来跑步还是休息。小H的体力限制了他跑步的距离。更具体地，如果小H选择在第 \(i\) 分钟内跑步，他可以在这一分钟内跑 \(D_i\) 米，并且他的疲劳度会增加 1。不过，无论何时小H的疲劳度都不能超过 \(M\)。如果小H选择休息，那么他的疲劳度就会每分钟减少 1，但他必须休息到疲劳度恢复到 0 为止。在疲劳度为 0 时休息的话，疲劳度不会再变动。晨跑开始时，小H的疲劳度为0。

　　还有，在 \(N\) 分钟的锻炼结束时，小H的疲劳度也必须恢复到 0，否则他将没有足够的精力来对付这一整天中剩下的事情。

　　请你计算一下，小H最多能跑多少米。

【输入格式】

　　第一行包含两个用空格隔开的整数 \(N\) 和 \(M\)；
　　接下来的 \(N\) 行，每行一个整数，其中第 \(i+1\) 为一个整数 \(D_i\)。

【输出格式】

　　输出一个整数，表示在满足所有限制条件的情况下，小H能跑的最大距离。

【输入输出样例】

　Input

5 2
5
3
4
2
10

　Output

9

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤10000\)，\(1≤D_i≤1000\)，\(1≤M≤500\)。

【来源】

　　Mr.he