問題文

高橋王国には $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}$
• 与えられる入力は全て整数

入力

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

$N$ $K$ $A_0$ $A_1$ $...$ $A_{N-1}$

出力

答えを出力せよ。

入力例 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