配点 : $300$ 点

問題文

数直線と $N$ 個のコマを用いて $1$ 人でゲームを行います。

はじめ、これらのコマをそれぞれ好きな整数座標に置きます。

このとき、同じ座標に複数のコマを置いても構いません。

以下の移動を繰り返して、座標 $X_1, X_2, ..., X_M$ の $M$ 個の地点全てをいずれかのコマで訪れることが目的です。

移動: コマを $1$ つ選び、そのコマの座標を $x$ とする。そのコマを座標 $x+1$ もしくは座標 $x-1$ に移動する。

ただし、最初にコマを置いた座標はその時点で訪れたとみなします。

目的を達成するまでに移動を行う回数の最小値を求めてください。

制約

• 入力はすべて整数である。
• $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$ は全て異なる。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$X_1$ $X_2$ $...$ $X_M$

出力

目的を達成するまでに移動を行う回数の最小値を出力せよ。

2 5
10 12 1 2 14

5

以下の手順で $5$ 回移動を行うと目的を達成でき、このときが最小です。

• はじめに $2$ 個のコマをそれぞれ座標 $1$, 座標 $10$ に置きます。
• 座標 $1$ のコマを座標 $2$ に移動します。
• 座標 $10$ のコマを座標 $11$ に移動します。
• 座標 $11$ のコマを座標 $12$ に移動します。
• 座標 $12$ のコマを座標 $13$ に移動します。
• 座標 $13$ のコマを座標 $14$ に移動します。

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

19

100 1
-100000

0