问题文

高桥王国有 $0$ 到 $N$ 的编号的 $N+1$ 个地方。

高桥君决定从城镇 $0$ 走到城镇 $N$，但他很缺乏运动。高桥君带了 $K$ 瓶空的瓶子。

当高桥君在城镇 $i(0 \leq i < N)$ 时，他可以进行以下两种行动：

• 花费 $A_i$ 日元，给一个空瓶子加水。这个行动可以无限次重复。
• 喝掉装有水的瓶子，让它变为空瓶。高桥君从城镇 $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