C - Installation of Relay Stations Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、一本の長い道路沿いに N 箇所の候補地点を持っています。候補地点 i（1 \leq i \leq N）は道路上の座標 X_i の位置にあります。各候補地点の座標はすべて異なりますが、番号の順に並んでいるとは限りません。

高橋君はこれらの候補地点からいくつかを選んで通信中継局を設置しようとしています。各候補地点には中継局を高々 1 つ設置でき、候補地点 i に中継局を設置するには建設費用 C_i がかかります。

通信中継局のネットワークを構築するためには、中継局を 2 箇所以上設置する必要があります。さらに、隣り合う中継局同士が互いに通信可能であるために、設置した中継局を座標順に並べたとき、隣接するどの 2 つの中継局間の距離も D 以下でなければなりません。ここで D はあらかじめ定められた正の整数です。

より正確には、以下の条件をすべて満たすように候補地点の部分集合を選ぶ必要があります。

  • 中継局を設置する候補地点を 2 箇所以上選ぶ。
  • 選んだ候補地点を座標の昇順に並べ、それらを p_1, p_2, \ldots, p_k（k \geq 2、X_{p_1} < X_{p_2} < \cdots < X_{p_k}）とする。このとき、すべての 1 \leq j \leq k-1 について X_{p_{j+1}} - X_{p_j} \leq D が成り立つ。

この条件を満たす選び方が 1 つ以上存在する場合は、建設費用の合計 \displaystyle\sum_{j=1}^{k} C_{p_j} の最小値を出力してください。条件を満たす選び方が存在しない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D \leq 10^9
  • 0 \leq X_i \leq 10^9（1 \leq i \leq N）
  • 1 \leq C_i \leq 10^9（1 \leq i \leq N）
  • X_i はすべて異なる。
  • 入力はすべて整数である。

入力

N D
X_1 C_1
X_2 C_2
\vdots
X_N C_N
  • 1 行目には、候補地点の数 N と、隣接する中継局間の距離として許される最大値 D が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目には、各候補地点の座標と建設費用が与えられる。
  • 1 + i 行目（1 \leq i \leq N）には、候補地点 i の座標 X_i と建設費用 C_i が、スペース区切りで与えられる。

出力

条件を満たす選び方が存在する場合は、建設費用の合計の最小値を 1 行で出力せよ。存在しない場合は -1 を 1 行で出力せよ。

入力例 1

4 5
10 8
3 4
7 6
20 1

出力例 1

10

入力例 2

5 3
0 10
10 20
20 30
30 40
40 50

出力例 2

-1

入力例 3

10 15
100 50
20 7
35 40
5 30
80 6
65 25
50 10
120 9
91 12
10 5

出力例 3

12

入力例 4

25 100
1000 50
150 70
230 5
330 40
800 3
760 90
15 100
95 2
410 15
510 60
600 7
700 80
900 1
1100 55
1205 20
1300 4
1400 100
45 35
275 6
365 22
455 8
555 9
655 10
745 11
845 12

出力例 4

4

入力例 5

1 1000000000
1000000000 1

出力例 5

-1

Score : 366 pts

Problem Statement

Takahashi has N candidate locations along a single long road. Candidate location i (1 \leq i \leq N) is at coordinate X_i on the road. The coordinates of all candidate locations are distinct, but they are not necessarily ordered by their index.

Takahashi plans to select some of these candidate locations and install communication relay stations. At most 1 relay station can be installed at each candidate location, and it costs C_i to install a relay station at candidate location i.

To build a network of communication relay stations, at least 2 relay stations must be installed. Furthermore, for adjacent relay stations to be able to communicate with each other, when the installed relay stations are arranged in coordinate order, the distance between any two adjacent relay stations must be at most D, where D is a predetermined positive integer.

More precisely, a subset of candidate locations must be selected satisfying all of the following conditions:

  • At least 2 candidate locations are selected for relay station installation.
  • When the selected candidate locations are arranged in ascending order of their coordinates, denoting them as p_1, p_2, \ldots, p_k (k \geq 2, X_{p_1} < X_{p_2} < \cdots < X_{p_k}), the condition X_{p_{j+1}} - X_{p_j} \leq D holds for all 1 \leq j \leq k-1.

If there exists at least one valid selection satisfying these conditions, output the minimum total construction cost \displaystyle\sum_{j=1}^{k} C_{p_j}. If no valid selection exists, output -1.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D \leq 10^9
  • 0 \leq X_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
  • All X_i are distinct.
  • All inputs are integers.

Input

N D
X_1 C_1
X_2 C_2
\vdots
X_N C_N
  • The first line contains the number of candidate locations N and the maximum allowed distance between adjacent relay stations D, separated by a space.
  • From the 2nd line to the (N + 1)-th line, the coordinate and construction cost of each candidate location are given.
  • The (1 + i)-th line (1 \leq i \leq N) contains the coordinate X_i and construction cost C_i of candidate location i, separated by a space.

Output

If a valid selection exists, output the minimum total construction cost in one line. If no valid selection exists, output -1 in one line.

Sample Input 1

4 5
10 8
3 4
7 6
20 1

Sample Output 1

10

Sample Input 2

5 3
0 10
10 20
20 30
30 40
40 50

Sample Output 2

-1

Sample Input 3

10 15
100 50
20 7
35 40
5 30
80 6
65 25
50 10
120 9
91 12
10 5

Sample Output 3

12

Sample Input 4

25 100
1000 50
150 70
230 5
330 40
800 3
760 90
15 100
95 2
410 15
510 60
600 7
700 80
900 1
1100 55
1205 20
1300 4
1400 100
45 35
275 6
365 22
455 8
555 9
655 10
745 11
845 12

Sample Output 4

4

Sample Input 5

1 1000000000
1000000000 1

Sample Output 5

-1