← 返回题目列表

AtCoder · awc0040_d

D. 穿越沙漠

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥正试图开车沿着一条道路穿越沙漠。高桥目前正值 0 并且需要在某个点到达绿洲 G。这里,点 x 表示距离处的位置 x 从起点开始。

高桥的车最初包含 F 升燃油。汽车可以行驶的距离 1 使用 1 升燃料,一旦燃料耗尽就无法继续前进。高桥只能从某一点向一个方向移动 0 朝点 G 并且无法回头。到达点 G 与 0 剩余燃料仍被视为已到达目的地。

有 N 点之间的加油站 0 和点 G。的 i第一个加油站位于点 P_i (0 < P_i < G)并且可以加油 R_i 升燃油。对于每个加油站,高桥都可以选择停留或经过。如果他停下来, R_i 升添加到他当前的燃油中。他最多可以在每个加油站停一次。此外,如果他路过,他必须加满油 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
  • 第一行包含 N 代表加油站数量, G 代表目的地的位置,以及 F 代表初始燃料,用空格分隔。
  • 从第 2 行到 (N + 1)第行,给出了各个加油站的信息。
  • 的 (i + 1)第行包含位置 P_i 的 i第加油站及加油量 R_i 可以在那里加油,中间用空格隔开。

输出

在一行中输出高桥需要停车到达点的最少加油站数量 G。如果无法到达,则输出 -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