Question
Balloon Packet Puzzle
Lily is organizing a festive celebration and needs a specific number of balloons to decorate the party: at least X green balloons and Y yellow balloons. However, in her town, green and yellow balloons only come in mixed packs, each with a different number of green and yellow balloons. There are N packs available, with each pack containing A[i] green balloons and B[i] yellow balloons.
What’s the minimum number of packs Lily needs to buy to make sure she has at least X green and Y yellow balloons for her party?
Input
The first line of input contains three space-separated integers X, Y, and N.
The next N line of input contains two space-separated integers each depicting the value of green and yellow balloons in the ith packet.
Constraints
1 ≤ N ≤ 300
1 ≤ X ≤ 300
1 ≤ Y ≤ 300
0 ≤ A[i], B[i] ≤ 300
The next N line of input contains two space-separated integers each depicting the value of green and yellow balloons in the ith packet.
Constraints
1 ≤ N ≤ 300
1 ≤ X ≤ 300
1 ≤ Y ≤ 300
0 ≤ A[i], B[i] ≤ 300
Output
Print the minimum number of packets required if is impossible to get at least X green and Y yellow balloons then print -1.
Note: Each packet can be used only once.
Note: Each packet can be used only once.
Example
Input
4 8 3
1 5
4 2
2 6
Output
2
Explanation
Taking packets 2nd and 3rd will give the needed number of balloons.
4 8 3
1 5
4 2
2 6
Output
2
Explanation
Taking packets 2nd and 3rd will give the needed number of balloons.