B - 自動ドア 解説 /

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

問題文

ABCマーケットは高橋王国で最も人気なスーパーマーケットです。 入り口は自動ドアになっています。

この自動ドアは人が前を通りかかると自動で開き、そこから T 秒後まで開き続け、その後自動的に閉じます。 ドアが開いている状態で新たに人が前を通りかかると、通りかかった時刻のさらに T 秒後まで開き続ける時間が延長されます。

今日はのべ N 人の客が自動ドアの前を通りかかりました。 i 番目の人が通りかかった時刻はABCマーケットが開店してから A_i 秒経った時刻です。

今日、この自動ドアが開いていた合計秒数を求めてください。

入力

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

N T
A_1
A_2
:
A_N
  • 1 行目に今日自動ドアの前を通りかかった人数を表す整数 N(1 ≦ N ≦ 10^5) とドアが開き続ける時間を表す整数 T(1 ≦ T ≦ 10^5) が空白区切りで与えられる。
  • 2 行目からの N 行のうち i 行目には i 番目の客が自動ドアの前を通りかかった時刻 A_i(1 ≦ A_i ≦ 10^6) が与えられる。
  • A_1 ≦ A_2 ≦ … ≦ A_N が成り立つ。

部分点

この問題には部分点が設定されている。

  • 1 ≦ T ≦ 100を満たすデータセットに正解した場合は 50 点が与えられる。
  • 1 ≦ T ≦ 10^5を満たすデータセットに正解した場合はさらに 50 点が与えられる。合計で100点となる。

出力

ドアが開いていた秒数を 1 行に出力せよ。 出力の末尾に改行を入れること。

入力例1

5 10
20
100
105
217
314

出力例1

45

時刻が 20 ～ 30、100 ～ 115、217 ～ 227、314 ～ 324 のときにドアが開いています。

入力例2

10 10
1
2
3
4
5
6
7
8
9
10

出力例2

19

入力例3

10 100000
3
31
314
3141
31415
314159
400000
410000
500000
777777

出力例3

517253