分数: 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