乌龟 Syrup 经常在他家旁边的一个池塘里游泳。这个池塘是在很久以前由冰川运动雕刻而成，狭长而笔直——形状几乎像一条河流，但水面平静安稳，足以让乌龟可以不受阻碍地向两个方向游动。
今天，Syrup 像往常一样待在池塘里时，瞥见了可怕的绿色小点——正在绽放的藻类孢子。经过一阵暴雨后，富含营养的土壤被冲刷进池塘，逐渐分解，为原本无害的本地藻类提供了养分，使其以极快的速度生长。如果放任不管，这些藻华可能会扩散到遮挡阳光，使其无法到达湖底的植物，从而引发生态失衡，使水体在数月内都受到破坏。
幸运的是，Syrup 对此并不陌生，并且有一个简单而有效的解决办法——把它们吃掉。他已经在这个线性的池塘中识别出 $N$ 个土壤径流点，藻类正从这些位置开始生长，可以从一端到另一端编号为 $1$ 到 $N$。第 $i$ 个点和第 $(i+1)$ 个点之间的距离为 $D_i$ 米，而 Syrup 当前位于第 $K$ 个位置，正好在他最先注意到的孢子旁边。他会先吞掉那个孢子，然后以每秒 $1$ 米的速度向两个方向中的一个游去，吃掉他经过的每一簇藻类，直到所有藻华都被清除。
每个径流点一开始有 $0$ 根藻丝，并且在 Syrup 到达之前，每秒会增加 $1$ 根藻丝。乌龟非常强壮，Syrup 吃下任意数量的藻丝都没有困难。然而，由于过度生长的藻类味道很差，他希望尽量减少在整个行程中吃掉的藻丝总数。你的任务是，在他选择最优路线的前提下，计算 Syrup 为清除池塘中所有藻类所必须吃掉的最少藻丝总数。
输入格式
你的程序必须从标准输入中读取数据。
第一行包含两个整数 $N$ 和 $K$。
第二行包含 $N-1$ 个整数，第 $i$ 个整数表示第 $i$ 个径流点与第 $i+1$ 个径流点之间的距离 $D_i$（单位：米）。
输出格式
你的程序必须向标准输出中写入结果。
输出应包含一行一个整数，表示 Syrup 为清除池塘中所有藻类所必须吃掉的最少藻丝总数。
实现细节
由于子任务 3、4、5、6 和 7 的输入规模可能非常大，建议使用带有快速输入例程的 C++ 来解决本题。科学委员会并未提供可以完全解决本题的 Java 或 Python 解法。
附件中提供了包含快速输入/输出模板的 C++ 和 Java 源代码文件，强烈建议使用这些模板。
如果你使用 Java 实现，请将文件命名为 Pond.java，并将主函数放在 Pond 类中。
子任务
每个测试点的最大运行时间为 1.5 秒，最大内存使用量为 1GiB。对于所有测试用例，输入均满足以下限制：
- $2 \le N \le 3 \times 10^5$
- $1 \le K \le N$
- $1 \le D_i \le 10^6$
你的程序将会在满足以下附加条件的测试数据上进行评测：
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 7 | $N \le 100$ |
| 2 | 11 | $N \le 2000$ |
| 3 | 10 | $1 \le K \le \min(N, 20)$ |
| 4 | 6 | $D_i = 1$ |
| 5 | 12 | $1 \le K \le \min(N, 2000)$，且对所有 $i \equiv 0 \pmod{100}$，有 $D_i \ge D_{i+1}$ |
| 6 | 25 | $1 \le K \le \min(N, 2000)$ |
| 7 | 29 | 无 |
样例数据
样例 1
该样例适用于子任务 1、2、3、6 和 7。
输入
7 3 5 2 4 2 2 5
输出
86
说明
最优路线是按顺序游经点 $3 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7 \rightarrow 1$，共吃掉 $0 + 2 + 8 + 10 + 12 + 17 + 37 = 86$ 根藻丝。
样例 2
该样例适用于子任务 1、2、3、6 和 7。
输入
9 5 4 3 2 1 1 3 6 10
输出
129
说明
最优路线是按顺序游经点 $5 \rightarrow 6 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 7 \rightarrow 8 \rightarrow 9$， 共吃掉 $0 + 1 + 3 + 5 + 8 + 12 + 26 + 32 + 42 = 129$ 根藻丝。
样例 3
该样例适用于所有子任务。
输入
6 4 1 1 1 1 1
输出
21 `
说明
一种最优路线是按顺序游经点 $4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 5 \rightarrow 6$，共吃掉 $0 + 1 + 2 + 3 + 7 + 8 = 21$ 根藻丝。