553. Minimum Number of Refueling Stops

A car starts with startFuel units of fuel and must reach a target distance; one unit of fuel drives one unit of distance. Along the way are gas stations, each given as [position, fuel], where stopping adds that fuel. Return the minimum number of stops to reach the target, or -1 if it is impossible. The input is JSON {target, startFuel, stations}.

Input: JSON {target, startFuel, stations}.

Output: Integer — the minimum stops, or -1.

Examples

Input: {"target":100,"startFuel":10,"stations":[[10,60],[20,30],[30,30],[60,40]]}
Output: 2
Explanation: Two well-chosen stops suffice.

Input: {"target":1,"startFuel":1,"stations":[]}
Output: 0
Explanation: Already enough fuel.

Input: {"target":100,"startFuel":1,"stations":[[10,100]]}
Output: -1
Explanation: Cannot even reach the first station.

Constraints

• 1<=target<=10^9
• 0<=startFuel<=10^9
• 0<=stations<=500

Asked by