有 $N$ 位村民（包括村长）住在数字村。有趣的是，他们所有的房子都在一条直线上。第 $i$ 位村民（$0 \le i < N$）的房子位于村长家以东恰好 $a_i$ 公里处。（为简化起见，第 $0$ 位村民是村长，因此 $a_0 = 0$。）

最近，数字村将举办一场锦标赛，村里的每个人都会参加。

为了方便村民，组织者计划建造 $K$ 个体育场。体育场可以建在村里的任何地方，甚至可以建在任何村民的房子所在的位置。

然而，组织者希望交通成本最小化。交通成本定义为 $\sum_{i=0}^{N-1} \min_{j=0}^{K-1} D(a_i, s_j)$，其中 $D(a_i, s_j)$ 是第 $i$ 位村民的房子与第 $j$ 个体育场之间的距离。

你的任务是计算最小交通成本（向下取整到最接近的整数），给定 $N$、$K$ 和 $a_i$。

输入格式

第一行包含两个正整数 $N, K$（$K \le N \le 3 \times 10^5$）。

第二行包含 $N$ 个非负整数 $a_0, a_1, \dots, a_{N-1}$（$0 = a_0 < a_1 < \dots < a_{N-1} \le 10^9$）。

输出格式

输出一个整数——最小交通成本，向下取整到最接近的整数。

样例

样例输入 1

5 2
0 4 7 9 10

样例输出 1

7

样例输入 2

9 3
0 1 10 11 20 21 22 30 32

样例输出 2

23