D - Installation of Radio Towers Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、とある地域の通信インフラ整備を担当するエンジニアです。

この地域には N 個の村があり、それらは一直線の道路に沿って、互いに異なる位置に配置されています。村 i は道路の起点から X_i メートルの位置にあり、標高は P_i メートルです。2つの村 i, j の間の距離は |X_i - X_j| メートルで定義されます（標高の差は距離に影響しません）。

高橋君は、すべての村に電波を届けるために、いくつかの村に電波塔を設置することになりました。電波塔は、標高が K メートル以上の村（すなわち P_i \geq K を満たす村 i）にのみ設置できます。標高は電波塔の設置可否にのみ関係し、電波の届く範囲には影響しません。

電波塔を設置した村から距離が D メートル以下であるすべての村は、その電波塔の電波を受信できます（電波塔を設置した村自身も、距離 0 として受信できます）。距離が D メートルを超える村には電波は届きません。電波の届く最大距離 D はすべての電波塔で共通です。

すべての村は、少なくとも1つの電波塔から電波を受信できなければなりません。

高橋君は、この条件を満たしながら、設置する電波塔の数を最小化したいと考えています。条件を満たす電波塔の配置が存在する場合は、必要な電波塔の最小数を求めてください。条件を満たす配置が存在しない場合は -1 を出力してください。

条件を満たせない例としては、電波塔を設置可能な村がどこにも存在しない場合や、電波塔を設置可能な村が存在してもどの電波塔からも距離 D 以内に入らない村がある場合が挙げられます。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq D \leq 10^9
  • 0 \leq X_i \leq 10^9
  • 1 \leq P_i \leq 10^9
  • X_i \neq X_j（i \neq j）
  • 入力はすべて整数
  • 村は位置 X_i の昇順に与えられるとは限らない

入力

N K D
X_1 P_1
X_2 P_2
\vdots
X_N P_N
  • 1 行目には、村の数 N、電波塔を設置できる標高の下限 K、電波塔の電波が届く最大距離 D が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各村の情報が与えられる。
  • 1 + i 行目では、村 i の道路の起点からの位置 X_i と標高 P_i が、スペース区切りで与えられる。

出力

すべての村に電波を届けられるような電波塔の配置が存在する場合は、必要な電波塔の最小数を 1 行で出力してください。存在しない場合は -1 を出力してください。

入力例 1

5 100 10
0 50
5 150
15 80
25 200
30 60

出力例 1

2

入力例 2

4 500 5
0 100
10 200
20 300
30 400

出力例 2

-1

入力例 3

10 50 15
0 100
8 30
20 60
25 40
35 80
50 55
60 20
75 90
85 45
100 70

出力例 3

4

Score : 400 pts

Problem Statement

Takahashi is an engineer responsible for developing the communication infrastructure of a certain region.

There are N villages in this region, placed at distinct positions along a straight road. Village i is located X_i meters from the starting point of the road and has an elevation of P_i meters. The distance between two villages i, j is defined as |X_i - X_j| meters (the difference in elevation does not affect the distance).

Takahashi needs to install radio towers in some of the villages in order to deliver radio signals to all villages. A radio tower can only be installed in a village whose elevation is at least K meters (that is, a village i satisfying P_i \geq K). Elevation only affects whether a radio tower can be installed or not, and does not affect the range of the radio signals.

All villages within a distance of D meters or less from a village where a radio tower is installed can receive the signal from that tower (the village where the tower is installed can also receive the signal, as the distance is 0). Villages at a distance exceeding D meters cannot receive the signal. The maximum signal range D is the same for all radio towers.

Every village must be able to receive a signal from at least one radio tower.

Takahashi wants to minimize the number of radio towers installed while satisfying this condition. If there exists a placement of radio towers that satisfies the condition, find the minimum number of radio towers needed. If no valid placement exists, output -1.

Examples of cases where the condition cannot be satisfied include: when there are no villages where a radio tower can be installed, or when there exists a village that cannot be within distance D of any village where a radio tower can be installed.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq D \leq 10^9
  • 0 \leq X_i \leq 10^9
  • 1 \leq P_i \leq 10^9
  • X_i \neq X_j (i \neq j)
  • All input values are integers
  • Villages are not necessarily given in ascending order of position X_i

Input

N K D
X_1 P_1
X_2 P_2
\vdots
X_N P_N
  • The first line contains the number of villages N, the minimum elevation K required to install a radio tower, and the maximum signal range D of a radio tower, separated by spaces.
  • From the 2nd line to the (N + 1)-th line, the information of each village is given.
  • The (1 + i)-th line contains the position X_i from the starting point of the road and the elevation P_i of village i, separated by spaces.

Output

If there exists a placement of radio towers that can deliver signals to all villages, output the minimum number of radio towers needed in one line. If no such placement exists, output -1.

Sample Input 1

5 100 10
0 50
5 150
15 80
25 200
30 60

Sample Output 1

2

Sample Input 2

4 500 5
0 100
10 200
20 300
30 400

Sample Output 2

-1

Sample Input 3

10 50 15
0 100
8 30
20 60
25 40
35 80
50 55
60 20
75 90
85 45
100 70

Sample Output 3

4