登录/注册
226. 远征 Expedition(挑战程序设计竞赛)
时间限制: C/C++ 1000 ms | 其他语言 2000 ms
内存限制: C/C++ 64 MB | 其他语言 128 MB
尝试次数: 306 | 通过次数: 88
尝试人数: 54 | 通过人数: 46
标签: 优先队列
难度: 中等
3
2

你需要驾驶一辆汽车行驶 LL 单位距离。

最开始时, 卡车上有 PP 单位的汽油。

汽车每开 11 单位距离需要消耗 11 单位的汽油。

如果在途中车上的汽油耗尽, 车就无法继续前行, 因而无法达到终点。

在途中一共有 NN 个加油站。第 ii 个加油站在距离 终点 AiA_i 单位距离的地方, 最多可以给汽车加 BiB_i 单位汽油。

假设卡车的燃油箱的容量是无限大的。问最少加多少次汽油可以达到终点 ?

无法达到请输出1-1

输入

  • 第一行是 NN,表示有多少个加油站
  • 接下来 NN 行,每行两个整数 Ai,BiA_i, B_i,表示每个加油站距离 终点 的位置,以及最多可以加多少油
  • 最后一行是 LL, PP
  • 1N21041 \leq N \leq 2*10^4
  • 1L1061 \leq L \leq 10^6
  • 1P1061 \leq P \leq 10^6
  • 1AiL1 \leq A_i \leq L
  • 1Bi1001 \leq B_i \leq 100

输出

  • 一个整数,表示最少加多少次油
样例 1
输入
4
4 4
5 2
11 5
15 10
25 10
输出
2