小雷的一筐竹
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