CF958E2.Guard Duty (medium)

Princess Heidi decided to give orders to all her K Rebel ship commanders in person. Unfortunately, she is currently travelling through hyperspace, and will leave it only at N specific moments _t_1, _t_2, ..., t__N. The meetings with commanders must therefore start and stop at those times. Namely, each commander will board her ship at some time t__i and disembark at some later time t__j. Of course, Heidi needs to meet with all commanders, and no two meetings can be held during the same time. Two commanders cannot even meet at the beginnings/endings of the hyperspace jumps, because too many ships in one position could give out their coordinates to the enemy.

Your task is to find minimum time that Princess Heidi has to spend on meetings, with her schedule satisfying the conditions above.

公主海蒂决定亲自向她所有的 $K$ 名反抗军舰船指挥官下达命令。不幸的是，她目前正穿越超空间，且仅会在 $N$ 个特定时刻 $t_1,\ t_2,\ \dots,\ t_N$ 离开超空间。因此，与指挥官们的会面必须在这些时刻开始和结束。具体而言，每名指挥官将在某个时刻 $t_i$ 登上她的飞船，并在之后的某个时刻 $t_j$ 离开。当然，海蒂必须与所有指挥官会面，且任意两次会面不能在同一时间段内进行。甚至在超空间跃迁的起始或结束时刻（即各 $t_i$ 处），也不能安排两名指挥官同时会面，因为同一位置聚集过多飞船可能向敌人暴露其坐标。

你的任务是：在满足上述约束条件的前提下，求出公主海蒂用于会面的最短总时间。

The first line contains two integers K, N (2 ≤ 2_K_ ≤ N ≤ 500000, K ≤ 5000). The second line contains N distinct integers _t_1, _t_2, ..., t__N (1 ≤ t__i ≤ 109) representing the times when Heidi leaves hyperspace.

第一行包含两个整数 $K$、$N$（满足 $2 \leq 2K \leq N \leq 500000$，且 $K \leq 5000$）。
第二行包含 $N$ 个互不相同的整数 $t_1,\,t_2,\,...,\,t_N$（$1 \leq t_i \leq 10^9$），表示 Heidi 离开超空间的时间。

Output only one integer: the minimum time spent on meetings.

输出一个整数：开会所花费的最少时间。

In the first example, there are five valid schedules: [1, 4], [6, 7] with total time 4, [1, 4], [6, 12] with total time 9, [1, 4], [7, 12] with total time 8, [1, 6], [7, 12] with total time 10, and [4, 6], [7, 12] with total time 7. So the answer is 4.

In the second example, there is only 1 valid schedule: [1, 2], [3, 4], [5, 6].

For the third example, one possible schedule with total time 6 is: [1, 3], [4, 5], [14, 15], [23, 25].

在第一个例子中，存在五个有效的调度方案：[1, 4], [6, 7]（总时间为 4），[1, 4], [6, 12]（总时间为 9），[1, 4], [7, 12]（总时间为 8），[1, 6], [7, 12]（总时间为 10），以及[4, 6], [7, 12]（总时间为 7）。因此答案为 4。

在第二个例子中，仅存在 1 个有效的调度方案：[1, 2], [3, 4], [5, 6]。

对于第三个例子，一个总时间为 6 的可能调度方案是：[1, 3], [4, 5], [14, 15], [23, 25]。