Minimum Stops for Ninja's Journey Problem Statement

Ninja wishes to travel from his house to a destination X miles away. He knows there are Y gas stations along the way, each station i located at a distance d[i] from the house with g[i] liters of gas available. His vehicle requires 1 liter of gas per mile.

Ninja starts with Z liters of fuel in his tank, which has infinite capacity. He can refuel his vehicle completely at any station if necessary.

Determine the minimum number of refueling stops Ninja must make to reach his destination.

Note:

If Ninja arrives at a station or the destination with no fuel, he can still refuel or be considered to have arrived.

Input:

The first line contains an integer T for the number of test cases to process.
Each test case has:
- A line with three integers: X (distance to destination), Y (number of stations), Z (starting fuel).
- Y pairs, each pair containing d[i] (distance to station) and g[i] (gas available at station).

Output:

For each test case, output a single integer, representing the minimum number of stops needed to reach the destination. Print each result on a new line.

Example:

Input:
X = 10, Y = 4, Stations = [[1, 6], [2, 3], [3, 3], [6, 4]], Z = 1
Output:
2

Explanation:

Starting with 1L, move to position 1: use 1L, refuel 6L. Move to position 6: use 5L, refuel 4L. Move to destination: use 4L. Total stops: 2.

Constraints:

• 1 <= T <= 10
• 1 <= X, Z <= 107
• 0 <= Y <= 105
• 1 <= d[i], g[i] <= 107
• Time limit: 1 second