E - 游乐园

得分：500分

问题描述

高桥来到了一个游乐园。
游乐园里有N个游乐项目。第i个游乐项目的乐趣初始为$a_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$

输出

输出高桥最后能够达到的满意度的最大可能值。

3 5
100 50 102

502

高桥应该玩第一种游乐项目两次，第三种游乐项目三次。
他最后的满意度为$(100+99)+(102+101+100)=502$。
无法达到满意度为503或更高的方式，所以答案是502。

2 2021
2 3

9

高桥可以选择玩的总次数少于$K$次。