游乐园

题目描述

高桥来到了一个游乐园。

游乐园里有 $N$ 个游乐设施。第 $i$ 个游乐设施的趣味度初始为 $a_i$。

当高桥乘坐第 $i$ 个游乐设施时，会发生以下一连串事件：

高桥的满足感增加当前第 $i$ 个游乐设施的趣味度。

然后，第 $i$ 个游乐设施的趣味度减少 $1$。

高桥的满足感初始为 $0$。他可以按任意顺序乘坐游乐设施，总次数最多为 $K$ 次。

高桥最终能达到的满足感的最大可能值是多少？

除了乘坐游乐设施之外，没有任何事情会影响高桥的满足感。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出高桥最终能达到的满足感的最大可能值。

样例

3 5
100 50 102

502

高桥应该乘坐第 1 个设施 2 次、第 3 个设施 3 次。

他将得到的满足感为 $(100+99)+(102+101+100)=502$。

无法得到 $503$ 或以上的满足感，所以答案是 $502$。

2 2021
2 3

9

高桥可以乘坐设施的总次数少于 $K$ 次。

数据范围

• $1 \le N \le 10^5$
• $1 \le K \le 2 \times 10^9$
• $1 \le A_i \le 2 \times 10^9$
• 输入中的所有值均为整数。