题目描述

路上有 $n$ 个车站，分别位于 $x_1, x_2, \dots, x_n$（$x_1 < x_2 < \dots < 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$。