题目描述

髙橋君は遊園地に遊びに行きました。
この遊園地には $N$ 個のアトラクションがあり、$i$ 個目のアトラクションの「楽しさ」の初期値は $A_i$ です。

髙橋君が $i$ 個目のアトラクションに乗ると、以下の現象が順番に起きます。

• 髙橋君の「満足度」に、$i$ 個目のアトラクションの現在の「楽しさ」が加算される。
• $i$ 個目のアトラクションの「楽しさ」が、$1$ 減少する。

髙橋君の「満足度」の初期値は $0$ です。髙橋君はアトラクションに合計 $K$ 回まで乗ることができます。
最終的な髙橋君の「満足度」の最大値はいくつですか？

なお、髙橋君の「満足度」はアトラクションに乗ること以外で変化しません。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

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

题目大意

高桥去游乐园玩。

有 $n$ 个游乐设施，每次玩时满意度加上此设施的乐趣值，同时设施的乐趣值减一，直到变成 $0$。

一个设施可以玩多次，求一共玩 $k$ 次后高桥满意度的最大值。

$1 \leq n \leq 1 \times 10^5$；

$1 \leq k,a_i \leq 2 \times 10^9$。

3 5
100 50 102

502

2 2021
2 3

9

提示

制約

• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ K\ \leq\ 2\ \times\ 10^9$
• $1\ \leq\ A_i\ \leq\ 2\ \times\ 10^9$
• 入力は全て整数

Sample Explanation 1

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

Sample Explanation 2

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