問題
$N \ $個のスイッチがあります。各スイッチにはONとOFFの二つの状態があり、はじめ全てのスイッチの状態はOFFです。スイッチを押すことでONとOFFの状態が切り替わりますが、$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 \ $となります。