A truck drives along a straight road from position 0 to position target. It starts with fuel litres and burns one litre per unit of distance. stations[i] = [position, litres] lists the fuel stations in increasing position order, all with position < target; stopping at a station adds its litres to the tank (no capacity limit). The truck may stop at a station only when it reaches it with fuel >= 0, and reaching a point with exactly zero fuel is allowed.
Return the minimum number of stops needed to reach target, or -1 if it is impossible.
Examples
Input: target = 120, fuel = 20, stations = [[15, 25], [40, 30], [60, 50], [95, 20]]
Output: 3
Explanation: stop at 15 (fuel reaches 45 from position 0), stop at 40 (75), stop at 60 (125),
which is enough to reach 120. No two stops suffice.
Input: target = 50, fuel = 50, stations = []
Output: 0
Input: target = 100, fuel = 1, stations = [[10, 100]]
Output: -1
Constraints
1 <= target <= 10**9,0 <= fuel <= 10**9,0 <= len(stations) <= 10**50 < position < target,1 <= litres <= 10**9- Target complexity: O(n log n).
Goals
- Postpone decisions: collect passed stations and refuel from them only when stuck
- Always refuel from the best station passed so far
- Detect impossibility when no passed station remains