题目描述

数轴上有 $n$ 块积木，第 $i$ 块积木在坐标 $x_i$ 上。一开始每块积木各自是一堆。

每次操作，你可以选择两堆相邻的积木（也就是它们之间没有其他积木堆），把其中一堆整体搬到另一堆所在的坐标，两堆合成一堆。把一堆积木从坐标 $X$ 搬到坐标 $Y$ 需要消耗 $|X-Y|$ 的能量。

Tom 想让积木堆的数量不超过 $m$，请你帮他求出需要消耗的最少能量。

输入格式

第一行两个整数 $n,m$，分别表示积木数量和允许的最大堆数。

第二行 $n$ 个整数 $x_1,x_2,\dots,x_n$，表示每块积木的坐标，相邻两个整数之间用一个空格隔开。

输出格式

一行，一个整数，表示最少需要消耗的能量。

样例

4 1
10 5 3 12

9

4 2
1 20 3 100

19

3 3
5 1 3

0

样例解释

样例 1 中，把坐标 $3$ 的积木并到 $5$（消耗 $2$），再把这一堆并到 $10$（消耗 $5$），最后并到 $12$（消耗 $2$），一共消耗 $9$ 能量，只剩 $1$ 堆。

样例 2 中，把坐标 $1$ 的积木并到 $3$（消耗 $2$），把坐标 $20$ 的积木并到 $3$（消耗 $17$），一共消耗 $19$ 能量，剩下坐标 $3$ 与 $100$ 两堆。

样例 3 中，已经有 $3$ 堆，不超过 $m=3$，不需要搬运，消耗 $0$。

数据范围与约定

对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le m\le n$，$-10^9\le x_i\le 10^9$。