问题 BH: Expedition

内存限制:32 MB 时间限制:3.000 S
评测方式:文本比较 命题人:
提交:240 解决:102

题目描述

一群母牛抓住卡车,冒险进入从林深处。不幸的是,司机跑过一块岩石时,卡车的油箱被刺穿。现在,卡车每行驶一段距离,就会泄漏1单位燃油。要修理卡车,母牛需要沿着一条蜿蜓曲折的道路驶向最近的城镇(相距不超过 1000000 单位)。在这条道路上,在城镇和卡车的当前位置之间,有N个(1≤N≤10000)加油站,卡车可以停下来获取更多的燃料(每站1~100 单位)。
从林对人类来说是一个危险的地方,对母牛来说更为危险。因此,母牛希望在前往小镇的途中尽可能少地停下加油。幸运的是,卡车上的油箱容量很大,以至于可以容纳的燃油量实际上没有限制。卡车目前离镇区L单位,有P单位燃料 (1≤P≤1000000)。
确定到达城镇,或者母牛根本无法到达城镇所需的最少停靠站数。

输入

第1行:一个整数N。
第2~N+1行:每行包含两个以空格分隔的整数,用于描述加油站:第一个整数是从城镇到停靠站的距离;第二个整数是该站的可用燃料量。
第N+2行:两个以空格分隔的整数L和P。

输出

第一行:一个整数,给出到达城镇所需的最少燃料停止数量。如果无法到达城镇,则输出-1。

样例输入 复制

4
4 4
5 2
11 5
15 10
25 10

样例输出 复制

2