問題文

高橋王国には 0 から N までの番号がついた N+1 箇所の町があります。

運動不足の高橋君は町 0 から町 N まで歩いて向かうことにしました。 高橋君は K 本の空のペットボトルを持っています。

高橋君は町 i(0 \leq i < N) にいるとき、以下の 2 種類の行動を行うことができます。

• A_i 円払い、1 本の空のペットボトルに水を注いでもらう。この行動は何度でも行うことができる。
• 水が入ったペットボトルを 1 本飲み干し、空のペットボトルにする。高橋君は町 i から町 i+1 へ移動する。

高橋君が町 N に到着するまでに必要な資金の最小値を求めてください。

制約

• 1 \leq K \leq N \leq 10^{5}
• 1 \leq A_i \leq 10^{9}
• 与えられる入力は全て整数

入力例 1

6 3
2 7 1 8 2 8

出力例 1

9

• 町 0 で 2 本のペットボトルに水を注いでもらう
• 町 1 へ移動する
• 町 2 へ移動する
• 町 2 で 3 本のペットボトルに水を注いでもらう
• 町 3 へ移動する
• 町 4 へ移動する
• 町 4 で 1 本のペットボトルに水を注いでもらう
• 町 5 へ移動する
• 町 6 へ移動する
• このように行動したとき 9 円で町 6 へ到着することが可能であり、これが最適です

入力例 2

13 4
4 3 9 1 3 8 2 6 11 9 2 15 40

出力例 2

26