TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1760
  • 题目
  • P1760逃亡
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    何老板抢劫了银行,他驾驶一辆卡车逃跑。卡车每行驶一公里就会消耗掉一升油。
    何老板需要把车开到最近的一个小镇,那里有同伙接应。从卡车当前位置到小镇的这条路上,分布着N个加油站 ,何老板可以停下来加油,但是这条路上每个加油站的油量不超过100升。
    警察正在追捕何老板,所以,何老板想让停下来加油的次数尽可能的少。幸运的是,卡车的油箱容量无限大。一开始卡车的油箱存有P升油,距离目标小镇L公里远。请计算何老板最少停下来加油几次?

    输入格式

    第一行,一个整数N
    接下来N行,每行两个整数,描述一个加油站的信息:第一个数表示加油站到目标小镇的距离,第二个数表示加油站可用的油量。
    接下来一行,两个空格间隔的整数L和P

    输出格式

    输出一行,一个整数,表示最少加油次数。如果无法到达目标小镇,输出-1。

    样例输入 1

    4
    4 4
    5 2
    11 5
    15 10
    25 10

    样例输出 1

    2

    样例输入 2

    10
    1 100
    2 100
    3 100
    4 100
    5 100
    6 100
    7 100
    8 100
    9 100
    10 100
    10000 10000

    样例输出 2

    0

    样例输入 3

    30
    272 10
    371 50
    495 56
    863 2
    887 11
    218 48
    503 33
    463 39
    570 80
    167 73
    579 41
    782 63
    544 14
    899 14
    117 51
    184 99
    246 3
    200 55
    338 7
    706 30
    625 92
    928 82
    479 7
    726 46
    967 28
    227 67
    550 99
    957 71
    535 2
    260 84
    1000 33

    样例输出 3

    16

    提示

    样例1说明
    开10公里, 加10 升油, 再开 4 公里, 加 5 升,最后开到目标小镇
    0 <= L <= 1,000,000
    1 <= N <= 10,000
    1 <= P <= 1,000,000