Minimum Refueling Stops

You are given an aircraft that needs to travel a distance of $D$ (final destination) starting with an initial fuel amount $F_0$. Along the journey, there are $N$ refueling stations. Each station is described by a pair $(d_i, f_i)$ where $d_i$ is the distance from the start and $f_i$ is the fuel provided at that station.

The problem asks you to determine the minimum number of refueling stops required to reach the destination. If it is impossible to reach the destination, output -1.

At each station, you may refuel any amount offered by the station, and you cannot refuel more than what is available there. The key idea is to use a greedy strategy with a max-heap data structure in order to always refuel from the station offering the most fuel whenever needed.

Mathematically, if you are currently at distance $d_{prev}$ with current fuel $F$, when you approach the next station at distance $d_i$, your fuel decreases by $(d_i - d_{prev})$. If at any point $F < 0$, you must refuel from the previously passed stations (in a greedy manner) until $F \ge 0$ or it becomes impossible to continue.

inputFormat

The input is given on standard input (stdin). The first line contains three space-separated integers:

• $F_0$ — the initial amount of fuel. • $D$ — the final destination distance. • $N$ — the number of refueling stations.

This is followed by $N$ lines, each containing two space-separated integers $d_i$ and $f_i$, where $d_i$ is the distance of the station from the start, and $f_i$ is the amount of fuel provided at that station.

outputFormat

Output a single integer on standard output (stdout): the minimum number of refueling stops required to reach the destination. If it is not possible to reach the destination, output -1.## sample

10 60 4
10 20
20 10
30 30
50 40

2