/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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
出力
最終的な髙橋君の「満足度」の最大値を出力せよ。
入力例 1
3 5 100 50 102
出力例 1
502
1 個目のアトラクションに 2 回、3 個目のアトラクションに 3 回乗ります。
最終的な「満足度」は、(100+99)+(102+101+100)=502 です。
「満足度」を 503 以上にする方法はないので、502 が答えになります。
入力例 2
2 2021 2 3
出力例 2
9
アトラクションに乗る合計回数は、K 回より少なくても構いません。
Score : 500 points
Problem Statement
Takahashi has come to an amusement park.
The park has N attractions. The fun of the i-th attraction is initially a_i.
When Takahashi rides the i-th attraction, the following sequence of events happens.
- Takahashi's satisfaction increases by the current fun of the i-th attraction.
- Then, the fun of the i-th attraction decreases by 1.
Takahashi's satisfaction is initially 0. He can ride the attractions at most K times in total in any order.
What is the maximum possible value of satisfaction Takahashi can end up with?
Other than riding the attractions, nothing affects Takahashi's satisfaction.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq K \leq 2 \times 10^9
- 1 \leq A_i \leq 2 \times 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the maximum possible value of satisfaction that Takahashi can end up with.
Sample Input 1
3 5 100 50 102
Sample Output 1
502
Takahashi should ride the first attraction twice and the third attraction three times.
He will end up with the satisfaction of (100+99)+(102+101+100)=502.
There is no way to get the satisfaction of 503 or more, so the answer is 502.
Sample Input 2
2 2021 2 3
Sample Output 2
9
Takahashi may choose to ride the attractions fewer than K times in total.