AT_abc216_e [ABC216E] Amusement Park

[problemUrl]: https://atcoder.jp/contests/abc216/tasks/abc216_e 髙橋君は遊園地に遊びに行きました。 この遊園地には $ N $ 個のアトラクションがあり、$ i $ 個目のアトラクションの「楽しさ」の初期値は $ A_i $ です。 髙橋君が $ i $ 個目のアトラクションに乗ると、以下の現象が順番に起きます。 - 髙橋君の「満足度」に、$ i $ 個目のアトラクションの現在の「楽しさ」が加算される。 - $ i $ 個目のアトラクションの「楽しさ」が、$ 1 $ 減少する。 髙橋君の「満足度」の初期値は $ 0 $ です。髙橋君はアトラクションに合計 $ K $ 回まで乗ることができます。 最終的な髙橋君の「満足度」の最大値はいくつですか？ なお、髙橋君の「満足度」はアトラクションに乗ること以外で変化しません。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

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

### 制約 - $ 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 $ 回より少なくても構いません。