配点 : $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$

出力

最終的な髙橋君の「満足度」の最大値を出力せよ。

3 5
100 50 102

502

$1$ 個目のアトラクションに $2$ 回、$3$ 個目のアトラクションに $3$ 回乗ります。 最終的な「満足度」は、$(100+99)+(102+101+100)=502$ です。 「満足度」を $503$ 以上にする方法はないので、$502$ が答えになります。

2 2021
2 3

9

アトラクションに乗る合計回数は、$K$ 回より少なくても構いません。