一辆卡车,初始时距离终点L,油量为P,在起点到终点途中有n个加油站,每个加油站油量有限,而卡车的油箱容量无限,卡车在行车途中,每走一个单位的距离消耗一个单位的油量,给定n个加油站距离起点的距离A[i]以及油存储量B[i]。问卡车是否能到达终点,如果可达,最少需要加多少次油,否则输出-1。输入不保证有序。
1<=n<=10000; 1<=L<=1000000; 1<=P<=1000000;1<=A[i]<L,1<=B[i]<=100。
第一行三个数L,P,n,以空格隔开,分别表示起点到终点的距离、现在的油量、中途加油站数; 之后n行,每行两个数A[i]和B[i],以空格隔开,表示该加油站到起点的距离和油存储量。
输出一个数,表示最少的加油次数。
100 15 2 15 75 90 25
2