C - Streamline 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 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

出力

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

入力例 1

2 5
10 12 1 2 14

出力例 1

5

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

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

入力例 2

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

出力例 2

19

入力例 3

100 1
-100000

出力例 3

0

Score : 300 points

Problem Statement

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.

Constraints

  • All values in input are integers.
  • 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 are all different.

Input

Input is given from Standard Input in the following format:

N M
X_1 X_2 ... X_M

Output

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

Sample Input 1

2 5
10 12 1 2 14

Sample Output 1

5

The objective can be achieved in five moves as follows, and this is the minimum number of moves required.

  • Initially, put the two pieces at coordinates 1 and 10.
  • Move the piece at coordinate 1 to 2.
  • Move the piece at coordinate 10 to 11.
  • Move the piece at coordinate 11 to 12.
  • Move the piece at coordinate 12 to 13.
  • Move the piece at coordinate 13 to 14.

Sample Input 2

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

Sample Output 2

19

Sample Input 3

100 1
-100000

Sample Output 3

0