003 - Switches

時間制限 2 秒 / メモリ制限 1024 MB / 得点 300 / x 9 /


TLE
2sec
MLE
1024MB
得点
300

問題

$N \ $個のスイッチがあります。各スイッチにはONOFFの二つの状態があり、はじめ全てのスイッチの状態はOFFです。スイッチを押すことでONOFFの状態が切り替わりますが、$i \ $番目のスイッチは最大で$ \ T_i \ $回までしか押すことができません。

最終的にONであるスイッチの個数が$ \ K \ $個以上であるようにしたいとき、スイッチを押す回数の合計の最大値を求めてください。

入力

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

$N \ K$
$T_1 \ T_2 \ \ldots \ T_N$

出力

答えを一行に出力せよ。出力の末尾には改行を入れること。

制約

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

入出力例

入力例

5 3
1 2 1 2 2

出力例

7

例として、それぞれのボタンを$ \ 1,2,1,2,1 \ $回押すことでON,OFF,ON,OFF,ONとなり$ \ 3 \ $個のスイッチがONとなるため条件を満たします。このときスイッチを押した回数の合計は$ \ 7 \ $回です。条件を満たすように$ \ 7 \ $回より多く押す方法は存在しないため答えは$ \ 7 \ $となります。