[Usaco2005 open]Expedition 探险
一群奶牛抢了一辆卡车,决定深入丛林探险。然而,由于驾驶技术太差,卡车撞上了岩石,导致油箱破裂。现在,卡车每行驶一个单位的距离就会漏掉一个单位的燃料。
为了修理卡车,奶牛们必须沿着一条漫长而曲折的道路前往最近的城市,城市距离当前位置不超过 个单位的距离。在当前位置和城市之间有 个加油站,奶牛可以在每个加油站停下,并获得 至 个单位的燃料。
丛林对人类来说十分危险,对奶牛来说尤其如此。因此,奶牛希望在前往城市的途中尽可能少地停站加油。幸运的是,卡车的油箱容量足够大,可以认为没有容量限制。
卡车当前距离城市 个单位,并拥有 个单位的燃料。请计算到达城市所需的最少停站次数;如果无法到达城市,则输出无法到达的结果。
输入格式
- 第 行:一个整数 ,表示加油站的数量。
- 第 至第 行:每行包含两个用空格分隔的整数,描述一个加油站。第一个整数表示该加油站距离城市的距离,第二个整数表示该加油站可以提供的燃料数量。
- 第 行:两个用空格分隔的整数 和 ,分别表示卡车当前距离城市的距离和初始燃料量。
输出格式
输出一个整数,表示卡车到达城市所需的最少停站次数。如果无法到达城市,则输出 。
样例输入
4
4 4
5 2
11 5
15 10
25 10
样例输出
2
数据范围
- ;
- ;
- 每个加油站提供的燃料数量为 至 。
来源与许可
本题为 USACO 2005 Open 试题「探险」,题面与测试数据整理自 BZOJ。
样例 1
输入
4
4 4
5 2
11 5
15 10
25 10
输出
2