AT_code_festival_2018_final_e Tough Journey

高桥王国有 $N+1$ 个编号为 $0$ 到 $N$ 的城镇。 因为缺乏锻炼，高桥君决定从城镇 $0$ 步行到城镇 $N$。他手上有 $K$ 个空的塑料瓶。 当高桥君在城镇 $i$（$0 \leq i < N$）时，可以进行以下两种操作： - 支付 $A_i$ 日元，将一只空的塑料瓶灌满水。这个操作可以进行任意多次。 - 喝掉一只装满水的塑料瓶，并将其变为空瓶。高桥君可以从城镇 $i$ 走到城镇 $i+1$。 请你求出高桥君到达城镇 $N$ 所需的最小资金。

输入通过标准输入给出，格式如下： > $N$ $K$ $A_0$ $A_1$ $\ldots$ $A_{N-1}$

请输出答案。

## 限制条件 - $1 \leq K \leq N \leq 10^{5}$ - $1 \leq A_i \leq 10^{9}$ - 所有输入均为整数 ## 样例解释 1 - 在城镇 $0$ 灌满 $2$ 个塑料瓶 - 走到城镇 $1$ - 走到城镇 $2$ - 在城镇 $2$ 灌满 $3$ 个塑料瓶 - 走到城镇 $3$ - 走到城镇 $4$ - 在城镇 $4$ 灌满 $1$ 个塑料瓶 - 走到城镇 $5$ - 走到城镇 $6$ - 按照上述方式操作，可以用 $9$ 日元到达城镇 $6$，这是最优解。 由 ChatGPT 4.1 翻译