B - Irrigation Sprinkler Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は、一直線の花壇に設置するスプリンクラーの配置を計画しています。

花壇は数直線上に沿って伸びており、花壇上には N 個の植え込みが左から順に配置されています。i 番目の植え込みの座標は X_i で、そこには P_i 本の花が植えられています。すべての植え込みは正の座標にあります。

高橋君は座標 0 の位置に水源を持っており、ここから正の方向に向かって水を送るパイプを伸ばし、パイプの先端にスプリンクラーを 1 台設置します。スプリンクラーは設置地点から正の方向に距離 D 未満の範囲に水を撒きます。なお、パイプは水をスプリンクラーまで送る役割のみを持ち、パイプの通る区間には散水されません。

具体的には、スプリンクラーを座標 s（s は 0 以上の任意の実数）に設置した場合、座標が s 以上 s + D 未満の範囲にある植え込みの花すべてに水やりができます。すなわち、植え込みの座標 X_i が s \leq X_i < s + D を満たすとき、その植え込みの P_i 本の花は水やりできたとみなします。この条件を満たさない植え込みの花は水やりできません。

高橋君は、スプリンクラーの設置位置 s を最適に選ぶことで、水やりできない花の本数を最小化したいと考えています。スプリンクラーは必ず 1 台設置しなければなりません。

水やりできない花の本数の最小値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D \leq 10^9
  • 1 \leq X_1 < X_2 < \cdots < X_N \leq 10^9
  • 1 \leq P_i \leq 10^9
  • 入力はすべて整数

入力

N D
X_1 P_1
X_2 P_2
:
X_N P_N
  • 1 行目には、植え込みの数を表す整数 N と、スプリンクラーの散水距離を表す整数 D が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各植え込みの座標と花の本数が与えられる。
  • 1 + i 行目では、i 番目の植え込みの座標を表す整数 X_i と、その植え込みに植えられている花の本数を表す整数 P_i が、スペース区切りで与えられる。

出力

水やりできない花の本数の最小値を 1 行で出力せよ。

入力例 1

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

出力例 1

10

入力例 2

4 3
2 10
5 20
6 5
9 15

出力例 2

25

入力例 3

12 10
1 4
4 8
9 3
13 20
18 7
21 15
27 6
31 12
36 5
42 18
48 9
55 11

出力例 3

76

入力例 4

25 50
3 12
17 40
28 7
44 25
61 33
79 18
95 50
123 9
146 21
170 60
199 14
225 32
260 45
288 11
319 27
347 36
380 8
415 55
451 19
490 24
530 42
575 13
621 31
670 48
725 16

出力例 4

591

入力例 5

1 1000000000
1000000000 1000000000

出力例 5

0

Score : 333 pts

Problem Statement

Takahashi is planning the placement of a sprinkler to be installed in a straight flower bed.

The flower bed stretches along a number line, and N shrubs are arranged on it from left to right. The i-th shrub is located at coordinate X_i and has P_i flowers planted in it. All shrubs are located at positive coordinates.

Takahashi has a water source at coordinate 0. From here, he will extend a pipe in the positive direction to supply water and install exactly one sprinkler at the end of the pipe. The sprinkler waters the area in the positive direction within a distance strictly less than D from its installation point. Note that the pipe only serves to deliver water to the sprinkler, and no watering occurs along the interval where the pipe passes.

Specifically, if the sprinkler is installed at coordinate s (where s is any non-negative real number), all flowers in the shrubs located at coordinates greater than or equal to s and less than s + D can be watered. That is, if the coordinate X_i of a shrub satisfies s \leq X_i < s + D, the P_i flowers in that shrub are considered watered. Flowers in shrubs that do not satisfy this condition cannot be watered.

Takahashi wants to minimize the number of flowers that cannot be watered by choosing the sprinkler installation position s optimally. Exactly one sprinkler must be installed.

Find the minimum number of flowers that cannot be watered.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D \leq 10^9
  • 1 \leq X_1 < X_2 < \cdots < X_N \leq 10^9
  • 1 \leq P_i \leq 10^9
  • All input values are integers.

Input

N D
X_1 P_1
X_2 P_2
:
X_N P_N
  • The first line contains an integer N, representing the number of shrubs, and an integer D, representing the watering distance of the sprinkler, separated by a space.
  • The next N lines (from the 2nd to the (N+1)-th line) provide the coordinates and the number of flowers for each shrub.
  • The (1+i)-th line contains an integer X_i, representing the coordinate of the i-th shrub, and an integer P_i, representing the number of flowers in that shrub, separated by a space.

Output

Print the minimum number of flowers that cannot be watered in a single line.

Sample Input 1

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

Sample Output 1

10

Sample Input 2

4 3
2 10
5 20
6 5
9 15

Sample Output 2

25

Sample Input 3

12 10
1 4
4 8
9 3
13 20
18 7
21 15
27 6
31 12
36 5
42 18
48 9
55 11

Sample Output 3

76

Sample Input 4

25 50
3 12
17 40
28 7
44 25
61 33
79 18
95 50
123 9
146 21
170 60
199 14
225 32
260 45
288 11
319 27
347 36
380 8
415 55
451 19
490 24
530 42
575 13
621 31
670 48
725 16

Sample Output 4

591

Sample Input 5

1 1000000000
1000000000 1000000000

Sample Output 5

0