Fewest Stops Across the Desert

A rally car must drive distance kilometres along a straight desert road. It starts with fuel litres in its tank and burns exactly one litre per kilometre. Along the road are fuel depots: depots is a list of (position, litres) tuples sorted by position, where position is the depot's distance from the start in kilometres. Stopping at a depot adds all of that depot's litres to the tank, which is big enough to hold any amount.

Write fewest_stops(distance, fuel, depots) that returns the smallest number of depot stops needed to reach the finish, or -1 if the finish cannot be reached. Arriving at a depot or at the finish with an empty tank still counts as arriving.

Examples

fewest_stops(120, 30, [(20, 15), (25, 40), (50, 10), (70, 50), (90, 20)])  # returns 2
fewest_stops(50, 50, [(10, 5)])                # returns 0
fewest_stops(100, 20, [(10, 30), (60, 100)])   # returns -1
fewest_stops(60, 20, [(20, 20), (40, 20)])     # returns 2

In the first example the car stops at kilometre 25 (40 litres, enough to reach kilometre 70) and at kilometre 70 (50 litres, enough for the last 50 kilometres). In the third example the car gets no further than kilometre 50, so the depot at kilometre 60 is out of reach.

Constraints

• 1 <= distance <= 10^9
• 0 <= fuel <= 10^9
• 0 <= len(depots) <= 100,000
• Depot positions are whole numbers with 0 < position < distance, strictly increasing
• 1 <= litres <= 10^9

Note

Trying every set of stops is far too slow for 100,000 depots.