问题1757--丛林探险(POJ 2431)

1757: 丛林探险(POJ 2431)

时间限制: 1 Sec  内存限制: 128 MB
提交: 10  解决: 9
[提交] [状态] [讨论版] [命题人:]

题目描述

一群人开着一辆卡车冒险进入丛林深处,卡车油箱坏了,每走1米就会漏1升油,他们需要到最近的城镇(距离不超过106米)修理卡车。卡车当前位置和城镇之间有N(1≤N≤104)个加油站,每个加油站都可以加油1~100升,卡车油箱容量没有限制。目前卡车距离城镇L米,有P升油(1≤P≤106)他们希望在前往城镇的路上尽可能少地停下加油,请给出到达城镇所需的最少加油次数。

输入

第1行包含单个整数N,表示加油站的数量。第2~N+1行,每行都包含两个整数,用于描述加油站,第1个整数是从城镇到加油站的距离,第2个整数是该加油站的可用油量。第N+2行,每行都包含两下整数L和P。

输出

输出到达城镇所需的最少加油次数,若无法到达城镇,则输出-1。

样例输入 Copy

4
4 4
5 2
11 5
15 10
25 10

样例输出 Copy

2

提示

题目来源POJ2431

来源/分类