Minimum Refueling Stops

A car starts at position 0 with start_fuel units of fuel; one unit of fuel moves it one mile. There are gas stations stations[i] = [position, fuel] sorted by position; stopping at a station lets you take all its fuel (your tank has no limit). Return the fewest stops needed to reach target, or -1 if impossible. If you can reach the target without stopping the answer is 0.

For target = 100, start_fuel = 10 and stations = [[10, 60], [20, 30], [30, 30], [60, 40]] the answer is 2.

The starter code tracks the best reach for every number of stops. It is correct but too slow for many stations.

Examples

Example 1

Input:

min_refuel_stops(100, 10, [[10, 60], [20, 30], [30, 30], [60, 40]])

Output:

2

Example 2

Input:

min_refuel_stops(100, 1, [[10, 100]])

Output:

-1

Constraints

• 1 <= target <= 10**9
• 0 <= start_fuel <= 10**9
• 0 <= len(stations) <= 100000, sorted by position, positions below target
• 1 <= fuel <= 10**9