B - プレイリストの最適化 解説 /

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

配点 : 333 点

問題文

高橋君は音楽フェスティバルのDJです。次のステージでは N 曲を再生する予定ですが、観客が違和感なく楽しめるように、曲の再生順序を工夫する必要があります。

各曲 i（1 \leq i \leq N）には「テンポ値」と呼ばれる整数 A_i が定められています。テンポ値は曲の雰囲気を数値化したもので、値が近い曲同士は似た印象を持ちます。また、非負整数 D が与えられます。テンポ値の差の絶対値が D 以下である 2 曲は「似ている」とみなされます。

高橋君は N 曲すべてをちょうど 1 回ずつ、好きな順序で再生します。再生順で j 番目に再生される曲のテンポ値を B_j とします。すなわち、(B_1, B_2, \ldots, B_N) は (A_1, A_2, \ldots, A_N) の並べ替え（多重集合として一致するもの）です。

再生順で j 番目の曲の「違和感スコア」を次のように定めます：

  • j = 1（1 曲目）のとき、違和感スコアは 0 です。
  • j \geq 2（2 曲目以降）のとき、過去に再生された曲のテンポ値 B_1, B_2, \ldots, B_{j-1} の中に、j 番目の曲と似ているもの、すなわち |B_j - B_k| \leq D を満たす k（1 \leq k \leq j-1）が存在するかどうかで次のように定まります：
  • 存在する場合：過去に似たテンポの曲が再生されていたため、観客は違和感を覚えません。違和感スコアは 0 です。
  • 存在しない場合：過去に再生されたどの曲ともテンポ値の差の絶対値が D より大きいため、直前の曲からの急激なテンポ変化が違和感として現れます。違和感スコアは |B_j - B_{j-1}| です。

全ての曲の違和感スコアの合計値を「違和感の総和」と呼びます。高橋君が再生順序を最適に選んだとき、違和感の総和の最小値を求めてください。

制約

  • 1 \leq N \leq 10^6
  • 0 \leq D \leq 10^9
  • 1 \leq A_i \leq 10^9（1 \leq i \leq N）
  • 入力は全て整数である

入力

N D
A_1 A_2 \ldots A_N
  • 1 行目には、曲の数を表す整数 N と、似ている曲かどうかを判定する閾値を表す非負整数 D が、スペース区切りで与えられる。
  • 2 行目には、各曲のテンポ値を表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

違和感の総和の最小値を整数として 1 行で出力せよ。

入力例 1

5 3
10 13 20 22 40

出力例 1

25

入力例 2

6 0
5 5 10 10 15 30

出力例 2

25

入力例 3

15 4
32 10 14 18 50 54 55 80 83 120 121 124 200 205 209

出力例 3

175

入力例 4

30 10
100 5 15 25 40 42 60 70 71 85 95 130 131 140 150 300 305 315 500 510 520 700 701 710 900 920 940 960 980 1000

出力例 4

882

入力例 5

1 1000000000
1000000000

出力例 5

0

Score : 333 pts

Problem Statement

Takahashi is a DJ at a music festival. He plans to play N songs in his next stage, but he needs to carefully arrange the playing order so that the audience can enjoy it without feeling any discomfort.

Each song i (1 \leq i \leq N) has an integer "tempo value" A_i. The tempo value quantifies the mood of the song, and songs with close tempo values have a similar impression. Additionally, a non-negative integer D is given. Two songs whose absolute difference in tempo values is at most D are considered "similar."

Takahashi will play all N songs exactly once in any order he chooses. Let B_j be the tempo value of the j-th song played in this order. That is, (B_1, B_2, \ldots, B_N) is a permutation of (A_1, A_2, \ldots, A_N) (as multisets).

The "discomfort score" of the j-th song in the playing order is defined as follows:

  • If j = 1 (the first song), the discomfort score is 0.
  • If j \geq 2 (the second song or later), it is determined by whether there exists a song similar to the j-th song among the previously played songs B_1, B_2, \ldots, B_{j-1} (i.e., whether there exists k (1 \leq k \leq j-1) such that |B_j - B_k| \leq D):
  • If it exists: Since a song with a similar tempo was played in the past, the audience does not feel discomfort. The discomfort score is 0.
  • If it does not exist: Since the absolute difference in tempo values between this song and any of the previously played songs is strictly greater than D, the sudden change in tempo from the immediately preceding song causes discomfort. The discomfort score is |B_j - B_{j-1}|.

The sum of the discomfort scores of all songs is called the "total discomfort." Find the minimum possible total discomfort when Takahashi chooses the playing order optimally.

Constraints

  • 1 \leq N \leq 10^6
  • 0 \leq D \leq 10^9
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.

Input

N D
A_1 A_2 \ldots A_N
  • The first line contains the integer N, representing the number of songs, and the non-negative integer D, representing the threshold for judging whether songs are similar, separated by a space.
  • The second line contains N integers A_1, A_2, \ldots, A_N, representing the tempo values of each song, separated by spaces.

Output

Print the minimum possible total discomfort as an integer in a single line.

Sample Input 1

5 3
10 13 20 22 40

Sample Output 1

25

Sample Input 2

6 0
5 5 10 10 15 30

Sample Output 2

25

Sample Input 3

15 4
32 10 14 18 50 54 55 80 83 120 121 124 200 205 209

Sample Output 3

175

Sample Input 4

30 10
100 5 15 25 40 42 60 70 71 85 95 130 131 140 150 300 305 315 500 510 520 700 701 710 900 920 940 960 980 1000

Sample Output 4

882

Sample Input 5

1 1000000000
1000000000

Sample Output 5

0