 New update is available. Click here to update.

# Ninja And Stops

Posted: 16 Mar, 2021
Difficulty: Hard

## PROBLEM STATEMENT

#### Now, you need to find out what is the minimum number of stops Ninja must make to reach his desired destination.

##### Note:
``````Note that if Ninja reaches a particular stop with no fuel, it can still fill his tank at that stop and continue his journey ahead. Similarly, if he reaches his destination with no fuel, it is still considered to have arrived.
``````
##### For example :
``````Given X = 10, Y = 4, ARR[Y] = {[1, 6], [2, 3], [3, 3], [6, 4]} and Z = 1
So the path followed in this case would look like this:

Ninja starts with 1L of gas.
Drives to the first gas station at position 1, using 1L of gas, then refueling with 6L of gas.
Then, drive to position 6, using 5L of gas, then refueling 4L in the current 1L of gas, making it a total of 5L of gas.
Finally, drive to the destination consuming 4L of gas.
So, Ninja made 2 refueling stops before reaching the destination. So, you need to print 2.
``````
##### Input Format:
``````The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains three space-separated integers ‘X’, ‘Y’ and ‘Z’, denoting distance in miles, number of gas stations, and starting fuel of the vehicle.

The next ‘Y’ lines of each test contain an array of ‘Y’ pairs where each pair denotes the distance from the house and available fuel for a refill.
``````
##### Output Format:
``````For each test case, you need to return a single integer denoting the minimum stops made to reach the destination.

Print the output of each test case in a separate line.
``````
##### Note:
``````You don’t need to print anything; It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 10
1 <= X, Z  <= 10^7
0 <= size of Y <= 10^5
1 <= Y1, Y2 <= 10^7

Time limit: 1 sec
``````