A car starts at position 0 with startFuel liters of fuel in its tank. It needs to travel to a position target miles east. Along the way there are gas stations, where stations[i] = [position_i, fuel_i] indicates that the i-th gas station is at position_i miles east and has fuel_i liters of fuel.
The car uses one liter of fuel per mile driven. When the car reaches a gas station it may stop and refuel, transferring all the fuel from that station into the car.
Return the minimum number of refueling stops the car must make to reach the target. If it cannot reach the target, return -1.
Example 1:
Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: We start with 10 liters of fuel. We drive to station 0 (position 10), refuel 60 liters (tank = 60). We drive to station 3 (position 60), refuel 40 liters (tank = 40). We drive to target (position 100). We made 2 refueling stops.
Example 2:
Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can only drive 1 mile, but the first station is 10 miles away. We cannot reach it.
Example 3:
Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without any refueling stops.
1 <= target, startFuel <= 10^90 <= stations.length <= 5001 <= position_i < target1 <= fuel_i < 10^9stations is sorted by position_i in ascending order