题目描述

路上有 $n$ 个车站，分别位于 $x_1$ ... $x_n$ ($x_1 < x_2 <$ ... $< x_n$) 处。

你的任务是选 $k$ 个放标志的地方 (标志的位置不局限于车站，也可以在其它地方) 。 令 $c(i,j)$ 表示第 $i$ 个站与第 $i$ 个和第 $j$ 个站之间离第 $i$ 个站最近的标记的距离，如果两个站直接没有标记，则 $c(i,j) = |x_i - x_j|$ ，则你需要合理选择标志的位置以最小化 $\sum_{i \neq j} c(i,j)$ 的值。

输入格式

输入包含多组测试数据，每组以两个整数 $n$ 和 $k$ 开始。
接下来的一行包含 $n$ 个整数 $x_1, \dots , x_n$ 。

输出格式

对于每个测试数据，输出一个整数，代表 $\sum_{i \neq j} c(i,j)$ 的最小值。

4 0
1 2 3 4
4 1
1 2 3 4

20
11

数据范围与提示

对于 $100\%$ 的数据， $0 \leq k \leq 200, 2 \leq n \leq 10000 , 0 \leq x_1 < x_2 < \ldots < x_n \leq 10^7$ 。

特别鸣谢楼天城和吉如一提供试题，数据。