#Pybt3313. 奶牛探险

    ID: 1034 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>堆二叉树赛制:ACM来源:wyfoj http://127.0.0.1

奶牛探险

奶牛探险

题目描述

一群奶牛抢了一辆卡车,决定前往丛林里探险。但是由于它们的驾驶技术太糟,所以每前进 1 公里就会漏掉 1 升的汽油。奶牛必须前往最近的城市。奶牛目前所在的位置距离城市有P公里,但邮箱里只有L升汽油了,所以她们可能在中途抛锚。不过奶牛知道路上有N个地点可以补充汽油,第i个补给点距离目的地城市有XiX_i 公里,可以为奶牛补给SiS_i 升汽油。对人类来说,丛林是个危险的地方,对奶牛来说也是这样。所以,她们尽量不会停车加油。幸运的是,这辆卡车的油箱非常大,多少油都能装得下。请算出奶牛至少要停几次才能到达终点,或者说明她们根本到不了那里。

输入格式

第一行:单个整数N,1 ≤ N ≤ 10000第二行到第N + 1行:第i + 1行有两个整数:XiX_i 和SiS_i ,1 ≤ XiX_i ≤ P,1 ≤SiS_i≤ 100第N + 2行:两个用空格分开的整数:P和L,1 ≤ L ≤ P ≤ 10610^6

输出格式

第一行:最少停车的次数,如果无法到达,输出−1

数据范围

(原站未提供,导入后需人工补齐)

样例

4
4 4
5 2
11 5
15 10
25 10
2


(前进10公里,加10升油,再前进4公里,加5升油,就能直接开到城市了)