题目描述

译自 NOISG 2021 Final T5. Pond

乌龟西拉普经常在房子旁边的池塘里游泳。这个池塘由远古冰川运动雕刻而成，狭长且笔直，形状几乎像一条河流，但水面平静，足以让乌龟不受阻碍地双向游泳。

今天，西拉普像往常一样在池塘中游泳时，瞥见了可怕的绿色斑点——一颗正在萌芽的藻类孢子。在大雨过后，冲入池塘的肥沃土壤逐渐分解，为通常无害的本地藻类提供了营养，使其以极快的速度生长。如果不加控制，这些藻类可能会疯狂扩散，阻挡阳光到达池塘底部的植物，导致生态失衡，影响水质长达数月。

幸运的是，西拉普对此并不陌生，他有一个简单而有效的解决办法——吃掉这些藻类。他在直线状的池塘中发现了 $N$ 个土壤流失点，这些点是藻类开始生长的位置，从一端到另一端编号为 $1$ 到 $N$。第 $i$ 个点与第 $(i+1)$ 个点之间的距离为 $D_i$ 米，西拉普当前位于第 $K$ 个点，旁边就是他最先发现的藻类孢子。他将首先吞下该处的藻类，然后以每秒 $1$ 米的速度向一个方向游去，沿途吃掉经过的每一簇藻类，直到所有藻类被清除。

每个流失点初始有 $0$ 条藻类链，每秒增加 $1$ 条，直到西拉普到达该点。乌龟体质强健，西拉普可以轻松吃掉任意数量的藻类链。然而，由于过多的藻类味道不佳，他希望尽量减少整个旅程中吃的藻类链总数。你的任务是找出西拉普清理池塘中所有藻类所需吃的最少藻类链总数，假设他选择了最佳路线。

输入格式

程序需从标准输入读取数据。

第一行包含两个整数 $N$ 和 $K$。

第二行包含 $N-1$ 个整数，第 $i$ 个整数表示 $D_i$，即流失点 $i$ 与 $i+1$ 之间的距离（单位：米）。

输出格式

程序需向标准输出输出结果。

输出一行，包含一个整数，表示西拉普清理池塘中所有藻类所需吃的最少藻类链总数。

7 3
5 2 4 2 2 5

86

最优路线是按顺序游过点 $3 \to 2 \to 4 \to 5 \to 6 \to 7 \to 1$，共吃掉 $0 + 2 + 8 + 10 + 12 + 17 + 37 = 86$ 条藻类链。

这个样例满足子任务 $1, 2, 3, 6, 7$ 的限制。

9 5
4 3 2 1 1 3 6 10

129

最优路线是按顺序游过点 $5 \to 6 \to 4 \to 3 \to 2 \to 1 \to 7 \to 8 \to 9$，共吃掉 $0 + 1 + 3 + 5 + 8 + 12 + 26 + 32 + 42 = 129$ 条藻类链。

这个样例满足子任务 $1, 2, 3, 6, 7$ 的限制。

6 4
1 1 1 1 1

21

一种最优路线是按顺序游过点 $4 \to 3 \to 2 \to 1 \to 5 \to 6$，共吃掉 $0 + 1 + 2 + 3 + 7 + 8 = 21$ 条藻类链。

这个样例满足所有子任务的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq K \leq N$
• $1 \leq D_i \leq 10^6$

详细子任务附加限制及分值如下表所示：