CF958E2 Guard Duty (medium)

公主 Heidi 决定亲自向她的 $K$ 位反叛舰队指挥官下达命令。不幸的是，她目前正在进行超空间旅行，并且只会在 $N$ 个特定时刻 $t_{1}, t_{2}, ..., t_{N}$ 离开超空间。因此，与指挥官的会面只能在这些时刻开始和结束。也就是说，每位指挥官会在某个时刻 $t_{i}$ 登上她的飞船，并在某个更晚的时刻 $t_{j}$ 离开。 当然，Heidi 需要与所有指挥官都见面，并且任何两个会面不能在同一时间进行。即使在超空间跳跃的开始或结束时，两位指挥官也不能同时会面，因为太多飞船聚集在同一位置可能会暴露他们的坐标给敌人。 你的任务是，在满足上述条件的前提下，求出公主 Heidi 用于会面的最短总时间。

第一行包含两个整数 $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 离开超空间的时刻。

仅输出一个整数，表示用于会面的最短总时间。

在第一个样例中，有五种有效的安排方式：$[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,2],[3,4],[5,6]$。 在第三个样例中，一种总时间为 6 的可行安排是：$[1,3],[4,5],[14,15],[23,25]$。 由 ChatGPT 4.1 翻译