127. Minimum Number of Refueling Stops

A car starts with startFuel and must reach target. Stations are [position, fuel] pairs. Each unit of fuel moves 1 unit. Return the minimum number of refueling stops to reach target, or -1 if impossible. Input: 'target, startFuel, [[pos,fuel],...]'.

Input: 'target, startFuel, [[pos,fuel],...]'.

Output: Integer stops or -1.

Examples

Input: 1, 1, []
Output: 0
Explanation: Already enough fuel.

Input: 100, 1, [[10,100]]
Output: -1
Explanation: Can't reach first station.

Input: 100, 10, [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: Refuel at stations to reach target.

Constraints

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

Asked by