Reference: LeetCode 871 — Minimum Number of Refueling Stops

A car starts at position ~0~ and must reach a destination at position ~target~.

The car initially contains ~startFuel~ units of fuel. Traveling one unit of distance consumes one unit of fuel.

There are ~n~ fuel stations along the route. Station ~i~ is located at position ~position_i~ and contains ~fuel_i~ units of fuel.

When the car reaches a station, it may stop and transfer all fuel from that station into its tank. The tank has unlimited capacity, and each station may be used at most once.

Find the minimum number of refueling stops required to reach the destination. Print ~-1~ if reaching the destination is impossible.

Input

• The first line contains two integers: ~target~ and ~startFuel~.
• The second line contains one integer ~n~.
• The following ~n~ lines each contain two integers: ~position_i~ and ~fuel_i~. The stations are given in strictly increasing order of position.

Output

• Print the minimum number of refueling stops, or ~-1~ if the destination cannot be reached.

Constraints

• ~1 \le target \le 10^9~
• ~1 \le startFuel \le 10^9~
• ~0 \le n \le 500~
• ~1 \le position_i < target~
• ~1 \le fuel_i \le 10^9~
• ~position_1 < position_2 < \ldots < position_n~

Example 1

Input:

100 10
4
10 60
20 30
30 30
60 40

Output:

2