P9833 [USACO05OPEN] Expedition G

A group of cows hijacked a truck and decided to go exploring in the woods. However, their driving skills were so bad that they damaged the fuel tank on the way, so the truck leaks $1$ unit of fuel for every $1$ unit of distance it travels. To repair the fuel tank, the cows must reach the nearest city (no more than $10^6$ units of distance away). Between the current position and the city, there are $n$ gas stations. The cows can refuel $1$ to $100$ units of fuel at a gas station. For humans, the woods are dangerous; for cows, even more so. Therefore, the cows want to stop for fuel as few times as possible. Luckily, the truck's fuel tank is very large, and you can assume its capacity is infinite. When the truck is $l$ units away from the city, it still has $p$ units of fuel left. You need to find the minimum number of stops needed for the cows to reach the city, or determine that they cannot reach the city at all.

The first line contains an integer $n$. Lines $2$ to $n+1$ each contain two integers separated by a space, describing a gas station. The first number is the distance of this gas station from the city, and the second number is the maximum amount of fuel that can be added at this station. Line $n+2$ contains two integers $l$ and $p$ separated by a space.

Output an integer representing the minimum number of stops the truck needs to make to reach the city. If it is impossible to reach, output `-1`.

For $100\%$ of the testdata, $1\leq n\leq 10^4$ and $1\leq p\leq 1000000$. Translated by ChatGPT 5