Amusement Park

题目描述

Takahashi 来到了一个游乐园。
公园里有 $N$ 个游乐设施。第 $i$ 个游乐设施的 乐趣值 初始为 $a_i$。 当 Takahashi 乘坐第 $i$ 个游乐设施时，会发生以下一序列事件。

Takahashi 的 满足度 增加当前第 $i$ 个游乐设施的乐趣值。 然后，第 $i$ 个游乐设施的乐趣值减少 $1$。

Takahashi 的满足度初始为 $0$。他最多可以按任意顺序乘坐游乐设施共计 $K$ 次。
Takahashi 最终能够得到的满足度的最大可能值是多少？ 除了乘坐游乐设施外，没有其他事情会影响 Takahashi 的满足度。

输入格式

输入按以下格式从标准输入给出： $N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出 Takahashi 最终能够得到的满足度的最大可能值。

3 5
100 50 102

502

2 2021
2 3

9

提示

$1 \leq N \leq 10^5$ $1 \leq K \leq 2 \times 10^9$ $1 \leq A_i \leq 2 \times 10^9$ 输入中的所有数值均为整数。Takahashi 应该乘坐第一个游乐设施两次和第三个游乐设施三次。
他最终将得到满足度 $(100+99)+(102+101+100)=502$。
不可能得到 $503$ 或更高的满足度，所以答案是 $502$。
Takahashi 也可以选择总共少于 $K$ 次乘坐游乐设施。

标签: AtCoder|abc216E

来源

AtCoder|abc216E