小雷的一筐竹

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

小雷为了证明自己雄风不减当年,一大清早背了一筐竹子给队友打枣去。谁知小雷身材太纤细,一不留神踩空掉进井里,在画圈圈诅咒偷井盖的小毛贼的同时小雷立马打电话求助楠神。楠神顺着小雷的咆哮(嚎哭)声赶了过来,看见狼狈的小雷,楠神笑得差点也滑下来,眼看笑得天快黑了,楠神打算抓紧把小雷救出来。已知井深h米,每节竹竿长L米,经过分类后一共有n种竹竿,ai表示第i种竹竿节数,bi表示第i种竹竿的根数,楠神通过把多根竹竿连接成长度大于等于井深的竹棍来救小雷,为了节省时间,楠神想要用尽量少的竹竿把小雷救出。你能帮楠神求出最少需要的竹竿数目么。

Input

多组输入,直到文件结束。
对于每组输入:

第一行包含三个整数:h(0 < = h < = 10^9),L (0 < = L < = 10^6),n(0 < = n < = 1000)。

接下来n行每行两个整数a(0 < = a < 10^6),b(0 < = b < = 10^6)。

Output

 对于每组输入,输出一个整数表示所需最少竹竿数。如果无法救出小雷,输出-1。

Sample Input

10 1 3
3 1
1 1
4 2
10 1 3
3 1
2 1
1 2
10 2 2
3 1
2 1

Sample Output

3
-1
2

Hint

 

Source

2015年第五届ACM趣味编程循环赛(第一场) by LeiQ