Refuelling on the way

greedy heap logistics interviews

A lorry drives along a straight road from the 0 km mark to the T km mark. Its tank holds F litres, a litre lasts a kilometre, and the tank is bottomless. There are filling stations along the way: at mark p you can take exactly g litres, all that is left in the station’s tank. What is the smallest number of stops needed to get there? If it is impossible, print −1.

In the first example it pays to stop at the first station and take 50 litres. Whoever drives to the farthest reachable station will get to the 50 mark, take 10 litres there and get stuck: the generous station is left behind.

Input

The first line holds T, F and the number of stations n (1 ≤ T, F ≤ 10⁹, 0 ≤ n ≤ 2·10⁵). Then come n lines with p and g (0 < p < T, 1 ≤ g ≤ 10⁹), the stations in increasing order of p.

Output

The smallest number of stops, or −1.

Examples

Example 1

Input

100 50 2
10 50
50 10

Output

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 10 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

You do not have to decide where to stop at the moment you pass a station. You can decide later, when the fuel runs out.

2The idea

Drive while there is fuel, and remember all the stations you have passed. When the next point is out of reach, pretend you filled up at the most generous of the stations passed, and take its fuel. Keep the passed stations in a heap by volume, the most generous on top.

3Walkthrough

Why is this optimal? Suppose we made k stops and reached mark x. Greed guarantees that among all ways of choosing k stations to the left of x, our set gives the most fuel: each time we took the largest of what was available. So nobody gets further on k stops either. This is the “greedy stays ahead” argument: at each step the greedy answer is at least as good as any other, and so on to the finish.

The rule “fill up at the farthest reachable station” looks reasonable, but it forgets the stations behind. The first example shows that it can get stuck where the road can be driven.

It is convenient to add the destination as a last station with zero litres: then the check “will we reach the end” is the same as for any station. The total fuel goes up to 2·10¹⁴, so Go needs int64.

3+Solution

4Complexity

Each station enters the heap once and leaves it at most once: O(n log n).

5Common mistakes

The farthest station. Drives past generous stations and gets stuck where the road can be driven: the first example, the sixth test.
Filling up wherever possible. Will get there if it is possible at all, but with many more stops.
The finish between stations. The check “is there enough to reach the destination” is needed just as the check for a station is: otherwise you can give an answer without getting there.

Algorithms behind it

PAR Technique Greedy algorithms The best step now with no looking back: when it is optimal, when almost, and how to prove it. usually O(n log n): a sort or a heap 2 problems DS Data structure Binary heap The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on. O(log n) 2 problems