1216 - 卡车加油
描述

一辆卡车,初始时距离终点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
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过次数 1