513. Minimum Number of Stops

0

Easy

A car needs to travel from a starting position to a destination that is target miles east of the starting position.
There are gas stations along the way, represented as an array called 'stations'. Each element in the 'stations' array is a subarray [position_i, fuel_i], where position_i represents the distance in miles of the i-th gas station from the starting position, and fuel_i represents the amount of fuel in liters available at that gas station.
The car initially has startFuel liters of fuel in its infinite tank. It consumes one liter of fuel per mile driven. When the car reaches a gas station, it can stop and refuel, transferring all the available fuel from the station into the car.
Note that if the car reaches a gas station with 0 fuel left, it can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

Input Format

The first line contains the target distance. The second line contains the initial amount of fuel in the car's tank. The third line contains a 2D array representing the gas stations along the way.

Output Format

Return the minimum number of refueling stops the car must make in order to reach its destination. If it is not possible to reach the destination, return -1.

Example

Input

100
1
[[10,60],[20,30],[30,30],[60,40]]

Output

2

Constraints

1 <= target, startFuel <= 10^9
0 <= stations.length <= 500
1 <= position_i < position_i+1 < target
1 <= fuel_i < 10^9

Loading...

View Submissions

Console