E - Tough Journey

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600

問題文

高橋王国には 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
  • 02 本のペットボトルに水を注いでもらう
  • 1 へ移動する
  • 2 へ移動する
  • 23 本のペットボトルに水を注いでもらう
  • 3 へ移動する
  • 4 へ移動する
  • 41 本のペットボトルに水を注いでもらう
  • 5 へ移動する
  • 6 へ移動する
  • このように行動したとき 9 円で町 6 へ到着することが可能であり、これが最適です

入力例 2

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

出力例 2

26