题目描述

数字村住着 $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, \cdots, a_{N-1}$（$0 = a_0 < a_1 < \cdots < a_{N-1} \le 10^9$）。

输出格式

输出一个整数——向下取整后的最小交通成本。

5 2
0 4 7 9 10

7

9 3
0 1 10 11 20 21 22 30 32

23

提示

翻译由 DeepSeek V4 Pro 完成