P1197

[Usaco2005 open]Expedition 探险

[Usaco2005 open]Expedition 探险

一群奶牛抢了一辆卡车,决定深入丛林探险。然而,由于驾驶技术太差,卡车撞上了岩石,导致油箱破裂。现在,卡车每行驶一个单位的距离就会漏掉一个单位的燃料。

为了修理卡车,奶牛们必须沿着一条漫长而曲折的道路前往最近的城市,城市距离当前位置不超过 10610^6 个单位的距离。在当前位置和城市之间有 NN 个加油站,奶牛可以在每个加油站停下,并获得 11 至 100100 个单位的燃料。

丛林对人类来说十分危险,对奶牛来说尤其如此。因此,奶牛希望在前往城市的途中尽可能少地停站加油。幸运的是,卡车的油箱容量足够大,可以认为没有容量限制。

卡车当前距离城市 LL 个单位,并拥有 PP 个单位的燃料。请计算到达城市所需的最少停站次数;如果无法到达城市,则输出无法到达的结果。

输入格式

  • 第 11 行:一个整数 NN,表示加油站的数量。
  • 第 22 至第 N+1N+1 行:每行包含两个用空格分隔的整数,描述一个加油站。第一个整数表示该加油站距离城市的距离,第二个整数表示该加油站可以提供的燃料数量。
  • 第 N+2N+2 行:两个用空格分隔的整数 LL 和 PP,分别表示卡车当前距离城市的距离和初始燃料量。

输出格式

输出一个整数,表示卡车到达城市所需的最少停站次数。如果无法到达城市,则输出 −1-1。

样例输入

4
4 4
5 2
11 5
15 10
25 10

样例输出

2

数据范围

  • 1≤N≤1041\le N\le 10^4;
  • 1≤L,P≤1061\le L,P\le 10^6;
  • 每个加油站提供的燃料数量为 11 至 100100。

来源与许可

本题为 USACO 2005 Open 试题「探险」,题面与测试数据整理自 BZOJ。

样例 1

输入

4
4 4
5 2
11 5
15 10
25 10

输出

2