P2620 Wormholes

applepi wants to travel through the universe. Of course, applepi knows this is possible because his special ability lets him observe wormholes in the universe. A wormhole is a shortcut opened in a dimension beyond three dimensions, allowing instantaneous movement from one place to another.

To simplify the problem, we set up a one-dimensional coordinate system, with Earth at position $0$, and applepi’s destination at a positive integer position $W$. In each unit time, applepi can move an integer no greater than $S$ toward the positive direction. A wormhole is represented as a pair $(B, E)$, meaning that if after a move applepi is at position $B$, he is immediately transported to position $E$. Note that if applepi passes through position $B$ during a move, he will not be transported because he moves extremely fast. Also, applepi cannot move in the negative direction, except when caused by a wormhole. Now applepi asks you to compute the minimum number of unit times needed to reach the destination.

The input contains multiple test cases. For each test case, the first line contains three positive integers $W, S, P$, representing the destination position, the movement limit, and the number of wormholes. The next $P$ lines each contain two integers $B$ and $E$, representing a wormhole. The last line of the input file is an integer $0$, indicating the end of input.

For each test case, output the result on a single line.

- For $30\%$ of the testdata, $W \le 1000$. - For $100\%$ of the testdata, $W \le 10^9$, $2 \le S \le 6$, $1 \le P \le 40$, there is no wormhole with $B = 0$ or $B = W$, and the input guarantees the destination is reachable. Translated by ChatGPT 5