AT_abc216_e [ABC216E] Amusement Park

题目描述

高桥君去游乐园玩了。
这个游乐园里有 $N$ 个游乐设施，第 $i$ 个游乐设施的“乐趣”初始值为 $A_i$。

当高桥君乘坐第 $i$ 个游乐设施时，会依次发生以下现象：

• 高桥君的“满足度”会增加第 $i$ 个游乐设施当前的“乐趣”值。
• 第 $i$ 个游乐设施的“乐趣”值减少 $1$。

高桥君的“满足度”初始值为 $0$。高桥君最多可以乘坐游乐设施 $K$ 次。
请问高桥君最终能获得的“满足度”的最大值是多少？

注意，高桥君的“满足度”只会因为乘坐游乐设施而变化。

输入格式

输入以如下格式从标准输入读入。

$N$ $K$ $A_1$ $A_2$ $A_3$ $\dots$ $A_N$

输出格式

请输出高桥君最终能获得的“满足度”的最大值。

输入输出样例 #1

输入 #1

3 5
100 50 102

输出 #1

502

输入输出样例 #2

输入 #2

2 2021
2 3

输出 #2

9

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq K \leq 2 \times 10^9$
• $1 \leq A_i \leq 2 \times 10^9$
• 输入均为整数

样例解释 1

可以选择第 $1$ 个游乐设施乘坐 $2$ 次，第 $3$ 个游乐设施乘坐 $3$ 次。最终的“满足度”为 $(100+99)+(102+101+100)=502$。没有办法让“满足度”达到 $503$ 或更高，因此答案为 $502$。

样例解释 2

总共乘坐游乐设施的次数可以少于 $K$。

由 ChatGPT 4.1 翻译