分数: 500 点
问题陈述
高桥来到了游乐园。
公园有 N 景点。的 有趣 的 i第一个景点最初是 a_i.
当高桥乘坐 i第一个景点,会发生以下事件序列。
- 高桥的 满意 增加了当前的乐趣 i- 第一个景点。
- 然后,乐趣 i第一个吸引力减少 1.
高桥的满意度最初是 0。他最多可以骑游景点
总共 K 次,顺序不限。
高桥最终能获得的最大可能满意度是多少?
除了乘坐景点之外,没有什么能影响高桥的满意度。
约束
- 1 \leq N \leq 10^5
- 1 \leq K \leq 2 \times 10^9
- 1 \leq A_i \leq 2 \times 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 \dots A_N
输出
打印高桥最终可能获得的最大可能满意度值。
示例输入 1
3 5 100 50 102
示例输出 1
502
高桥应该乘坐第一个景点两次,第三个景点三次。
他最终会得到满意的结果 (100+99)+(102+101+100)=502.
没有办法得到满足 503 或更多,所以答案是 502.
示例输入 2
2 2021 2 3
示例输出 2
9
高桥可能选择乘坐的景点少于 总共 K 次。