D - Crossing the Desert Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は砂漠の一本道を車で横断しようとしています。高橋君は現在地点 0 におり、地点 G にあるオアシスまでたどり着く必要があります。ここで、地点 x は出発地点からの距離が x である位置を表します。

高橋君の車には最初 F リットルの燃料が入っています。車は 1 リットルの燃料で距離 1 だけ進むことができ、燃料が尽きるとそれ以上進むことはできません。高橋君は地点 0 から地点 G に向かって一方向にのみ進み、後戻りすることはできません。地点 G に燃料がちょうど 0 の状態で到達した場合も、たどり着いたものとみなします。

地点 0 と地点 G の間には N 個の給油所があります。i 番目の給油所は地点 P_i（0 < P_i < G）にあり、R_i リットルの燃料を補給することができます。高橋君は各給油所について、立ち寄るか通過するかを選ぶことができます。立ち寄った場合、現在の燃料に R_i リットルが加算されます。各給油所には高々 1 回しか立ち寄ることができません。また、立ち寄った場合は必ず R_i リットル全量を補給するものとします（一部だけ補給することはできません）。なお、車の燃料タンクの容量に上限はなく、補給によって燃料がいくら増えても問題ありません。燃料がちょうど 0 の状態で給油所の地点に到達した場合でも、その給油所に立ち寄ることができます。

高橋君が地点 G のオアシスにたどり着くために、立ち寄る必要がある給油所の最小個数を求めてください。ただし、どのように給油所に立ち寄っても地点 G にたどり着けない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq G \leq 10^9
  • 0 \leq F \leq 10^9
  • 1 \leq P_i < G (1 \leq i \leq N)
  • 1 \leq R_i \leq 10^9 (1 \leq i \leq N)
  • P_i \neq P_j (i \neq j)
  • 入力はすべて整数

入力

N G F
P_1 R_1
P_2 R_2
\vdots
P_N R_N
  • 1 行目には、給油所の個数を表す N、目的地の位置を表す G、初期燃料を表す F が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目には、各給油所の情報が与えられる。
  • i + 1 行目では、i 番目の給油所の位置 P_i と、そこで補給できる燃料の量 R_i がスペース区切りで与えられる。

出力

高橋君が地点 G にたどり着くために立ち寄る必要がある給油所の最小個数を 1 行で出力してください。たどり着けない場合は -1 を出力してください。

入力例 1

3 10 4
4 3
6 2
7 3

出力例 1

2

入力例 2

3 15 4
3 2
6 1
10 10

出力例 2

-1

入力例 3

8 60 15
10 10
14 5
20 12
25 8
32 15
40 4
45 10
52 8

出力例 3

4

入力例 4

15 120 20
58 4
8 6
90 6
35 12
107 5
18 15
73 8
50 20
13 4
98 15
42 7
81 9
27 5
65 10
113 10

出力例 4

9

入力例 5

1 2 2
1 1

出力例 5

0

Score : 400 pts

Problem Statement

Takahashi is attempting to cross a desert along a single road by car. Takahashi is currently at point 0 and needs to reach an oasis at point G. Here, point x represents the position at distance x from the starting point.

Takahashi's car initially contains F liters of fuel. The car can travel a distance of 1 using 1 liter of fuel, and cannot proceed further once the fuel runs out. Takahashi can only travel in one direction from point 0 toward point G and cannot turn back. Arriving at point G with exactly 0 fuel remaining is still considered as having reached the destination.

There are N gas stations between point 0 and point G. The i-th gas station is located at point P_i (0 < P_i < G) and can refuel R_i liters of fuel. For each gas station, Takahashi can choose to either stop by or pass through. If he stops by, R_i liters are added to his current fuel. He can stop at each gas station at most once. Additionally, if he stops by, he must refuel the full R_i liters (partial refueling is not possible). Note that there is no upper limit on the car's fuel tank capacity, so there is no problem regardless of how much fuel increases through refueling. Even if Takahashi arrives at a gas station's location with exactly 0 fuel, he can still stop at that gas station.

Find the minimum number of gas stations Takahashi needs to stop at in order to reach the oasis at point G. If it is impossible to reach point G regardless of which gas stations he stops at, output -1.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq G \leq 10^9
  • 0 \leq F \leq 10^9
  • 1 \leq P_i < G (1 \leq i \leq N)
  • 1 \leq R_i \leq 10^9 (1 \leq i \leq N)
  • P_i \neq P_j (i \neq j)
  • All inputs are integers

Input

N G F
P_1 R_1
P_2 R_2
\vdots
P_N R_N
  • The first line contains N representing the number of gas stations, G representing the position of the destination, and F representing the initial fuel, separated by spaces.
  • From the 2nd line to the (N + 1)-th line, the information of each gas station is given.
  • The (i + 1)-th line contains the position P_i of the i-th gas station and the amount of fuel R_i that can be refueled there, separated by spaces.

Output

Output in one line the minimum number of gas stations Takahashi needs to stop at to reach point G. If it is impossible to reach, output -1.

Sample Input 1

3 10 4
4 3
6 2
7 3

Sample Output 1

2

Sample Input 2

3 15 4
3 2
6 1
10 10

Sample Output 2

-1

Sample Input 3

8 60 15
10 10
14 5
20 12
25 8
32 15
40 4
45 10
52 8

Sample Output 3

4

Sample Input 4

15 120 20
58 4
8 6
90 6
35 12
107 5
18 15
73 8
50 20
13 4
98 15
42 7
81 9
27 5
65 10
113 10

Sample Output 4

9

Sample Input 5

1 2 2
1 1

Sample Output 5

0