Problem B

Banana Party

Problem Description

Chimp loves banana. He can’t walk without eating banana. He needs 1 banana to walk 1 km, but he needs none to climb a banana tree.

One day, Chomp, a friend of Chimp, invites Chimp to a Banana Party at his house. Unfortunately, Chomp’s house is pretty far from Chimp’s and there’s only one route. So he has to make sure that he will have enough banana supply to walk to Chomp’s (remember, he can’t walk without banana).

If all bananas in his house is not enough to get him to Chomp’s, he can stop by to climb and collect bananas from banana trees along the route anytime. Chimp knows all banana trees’ locations and the number of bananas on each tree. Chimp is in a hurry, so he doesn’t want to stop more than what is necessary.

Write a program to help Chimp finds the minimum number of stops (to climb and collect banana) needed to travel from his house to Chomp’s. Assume that Chimp can bring an infinite amount of banana with him (don’t ask how). By the way, Chimp and Chomp are monkeys (in case you wonder).

Input Speficication

The first line of input contains an integer T, the number of test cases follow.

Each case begins with three integers, H (0 <= H <= 100) the number of banana in his house, L (0 <= L <= 10000) the Chomp’s house location in km, and N (0 <= N <= 100) the number of banana trees along the route. The next N lines each contain two integers, P (0 <= P <= 100) the distance of i-th banana tree from Chimp’s house and B (0 <= B <= 100) the number of bananas in that tree. Chimp’s house is at 0 km.

Output Speficication

For each case, print in a single line, the number minimum number of stop needed by Chimp to travel from his house to Chomp’s. If there’s no way he can arrive at Chomp’s house, print -1.

2
8 10 3
1 3
4 3
7 1
2 10 1
3 4

1
-1