AT_code_festival_2018_final_e Tough Journey

[problemUrl]: https://atcoder.jp/contests/code-festival-2018-final/tasks/code_festival_2018_final_e 高橋王国には $ 0 $ から $ N $ までの番号がついた $ N+1 $ 箇所の町があります。 運動不足の高橋君は町 $ 0 $ から町 $ N $ まで歩いて向かうことにしました。 高橋君は $ K $ 本の空のペットボトルを持っています。 高橋君は町 $ i(0\ \leq\ i\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ A_0 $ $ A_1 $ $ ... $ $ A_{N-1} $

答えを出力せよ。

### 制約 - $ 1\ \leq\ K\ \leq\ N\ \leq\ 10^{5} $ - $ 1\ \leq\ A_i\ \leq\ 10^{9} $ - 与えられる入力は全て整数 ### Sample Explanation 1 \- 町 $ 0 $ で $ 2 $ 本のペットボトルに水を注いでもらう - 町 $ 1 $ へ移動する - 町 $ 2 $ へ移動する - 町 $ 2 $ で $ 3 $ 本のペットボトルに水を注いでもらう - 町 $ 3 $ へ移動する - 町 $ 4 $ へ移動する - 町 $ 4 $ で $ 1 $ 本のペットボトルに水を注いでもらう - 町 $ 5 $ へ移動する - 町 $ 6 $ へ移動する - このように行動したとき $ 9 $ 円で町 $ 6 $ へ到着することが可能であり、これが最適です