题目描述

We will play a one-player game using a number line and $N$ pieces.

First, we place each of these pieces at some integer coordinate.

Here, multiple pieces can be placed at the same coordinate.

Our objective is to visit all of the $M$ coordinates $X_1, X_2, ..., X_M$ with these pieces, by repeating the following move:

Move: Choose a piece and let $x$ be its coordinate. Put that piece at coordinate $x+1$ or $x-1$.

Note that the coordinates where we initially place the pieces are already regarded as visited.

Find the minimum number of moves required to achieve the objective.

我们将用一条数线和 $N$ 个棋子玩一个单人游戏。

首先，我们将每个棋子放在某个整数坐标处。

在这里，可以在同一坐标上放置多个棋子。

我们的目标是通过重复下面的棋步，用这些棋子访问所有 $M$ 坐标 $X_1, X_2, ..., X_M$ ：

移动*：选择一颗棋子，让 $x$ 成为它的坐标。将该棋子置于坐标 $x+1$ 或 $x-1$ 处。

请注意，我们最初放置棋子的坐标已被视为已访问过的坐标。

找出实现目标所需的最少步数。

输入格式

输入内容按以下格式标准输入：

$N$ $M$
$X_1$ $X_2$ $...$ $X_M$

输出格式

找出实现目标所需的最少移动次数。

样例 #1

样例输入 #1

2 5
10 12 1 2 14

样例输出 #1

5

样例 #2

样例输入 #2

3 7
-10 -3 0 9 -100 2 17

样例输出 #2

19

样例 #3

样例输入 #3

100 1
-100000

样例输出 #3

0

说明

数据规模与约定

• 所有输入值均为整数。
• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $-10^5 \leq X_i \leq 10^5$
• $X_1, X_2, ..., X_M$ 都是不同的。

样例 $1$ 解释

如下所示，目标可以在五步之内实现，这也是所需的最少步数。

• 首先将两颗棋子置于坐标 $1$ 和 $10$ 处。
• 将位于坐标 $1$ 的棋子移动到 $2$ 。
• 将坐标 $10$ 处的棋子移动到 $11$ 。
• 移动坐标 $11$ 处的棋子至 $12$ 。
• 移动坐标 $12$ 处的棋子至 $13$ 。
• 将坐标 $13$ 处的棋子移动到 $14$ 。