Description

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.

Input Format

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.

Output Format

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

28 3 5
2 18
5 13
12 6
17 25
20 15
50 6 1
9 45
0

４
３

Hint

• 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