矿业调度（Mining）

题目描述

王国境内有 (N) 个矿点，编号为 (1) 到 (N)。国王每天可以选择一个矿点开采。对于第 (i) 个矿点：

• 第一次开采时，可以获得 (A_i) 单位金矿。
• 一旦开始开采，该矿点每天可获得的金矿量减少 (1)：首次开采的次日为 (A_i-1)，再下一日为 (A_i-2)，依此类推。
• 每次开采都需要支付 (i-1) 单位金矿作为运输成本。

当天的净收益 = 当天采获的金矿量 − 运输成本。

国王最多有 (M) 天可以开采，每天至多选择一个矿点。如果所有矿点的当天净收益都不大于 (0)，便停止开采。

例如，有两个矿点，(A_1=4)、(A_2=2)，可开采时间为 (M=10) 天。前四天连续开采矿点 (1)，净收益为 (4+3+2+1=10)。第五天首次开采矿点 (2)，净收益为 (2-(2-1)=1)。此后没有矿点能带来正收益，因此最终总净收益为 (11)。

请计算采用最佳策略时，国王在 (M) 天内最多能获得多少净收益。

输入格式

输入共两行：

• 第一行包含两个整数 (N,M)，分别表示矿点数量和最多可开采的天数，满足 (1\le N\le10^5)、(1\le M\le100)。
• 第二行包含 (N) 个整数 (A_1,A_2,\ldots,A_N)，其中 (1\le A_i\le10^6)，表示各矿点首次开采时可获得的金矿量。

输出格式

输出一个整数，表示 (M) 天内能够获得的最大净收益。

样例 1

输入

5 3
7 3 5 9 10

输出

19

说明

前两天开采矿点 (1)，分别获得 (7) 和 (6) 的净收益；第三天首次开采矿点 (4)，净收益为 (9-(4-1)=6)。总净收益为 (7+6+6=19)。

样例 2

输入

2 10
4 2

输出

11

评分说明

每组包含多笔测试数据，只有答对该组的全部数据才能获得对应分数。