配点 : 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