题目描述

给定 $n$ 个数字，需要将它们分成 $k$ 个非空组（每组至少包含一个数字）。对于任意一个组，其贡献值定义为该组内最大数字与最小数字的差值。例如，若某组数字为 $\{1,2,3,4\}$，则该组的贡献值为 $4-1=3$。

请你设计分组方案，使得所有组的贡献值之和达到最大，并输出这个最大值。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示数字的个数和需要分成的组数。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示给定的 $n$ 个数字。

输出格式

一行一个整数，表示所有组贡献值之和的最大值。

样例输入 1

4 2
1 2 3 4

样例输出 1

4

样例解释 1

分成 $\{1,3\}$ 和 $\{2,4\}$，贡献值分别为 $3-1=2$ 和 $4-2=2$，总和为 $2+2=4$；

样例输入 2

5 3
1 3 5 7 9

样例输出 2

12

数据范围

• $1 \leq k \leq n \leq 10^5$
• $1 \leq a_i \leq 10^9$