E - Tough Journey
Editorial
/
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
- 町 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