← 返回题目列表

AtCoder · abc216_e

H. 游乐园

中文机器翻译题面 查看原题

分数: 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 次。