A delivery drone must travel a straight route of length D kilometers. It starts with a battery that can cover R kilometers before recharging. Along the route there are n charging pads, given in order of increasing distance from the start; pad i sits at distance dist_i from the start (with 0 < dist_i < D) and, if the drone stops there, instantly adds boost_i kilometers to the drone's remaining range. The drone can only reach a pad if the pad's distance is within its current achievable range; it may choose to stop at a reachable pad or skip it. Find the minimum number of charging stops needed for the drone to reach or pass distance D. If it is impossible even using every reachable pad, print -1.
Input format
Line 1: three integers D R n.
Next n lines: two integers dist_i boost_i for each charging pad, given in strictly increasing order of dist_i.
Output format
A single integer: the minimum number of charging stops needed to reach distance D, or -1 if it is impossible.
Constraints
- 1 <= D <= 200
- 1 <= R <= 100
- 0 <= n <= 8
- 0 < dist_i < D, 1 <= boost_i <= 100