Description

为了简化问题，我们建立一个一维坐标系，地球的位置为 $0$，而applepi 的目的地的位置是一个正整数 $W$。

在每一个单位时间里，applepi 可以向正方向移动不超过 $S$ 的一个整数。虫洞可以被表示为二元组 $(B, E)$，即如果在某次移动之后 applepi 在位置 $B$，那么 applepi 就会被立刻传送到位置 $E$。

注意，applepi 在移动过程中如果经过位置 $B$，由于applepi 的速度极快是不会被传送的。而且，applepi 不能够向负方向移动，但是虫洞引起的除外。

现在applepi 想请你帮助他计算一下他至少需要多少个单位时间才能够到达目的地。

Input Format

输入包含多组测试数据。

每组测试数据的第一行是三个正整数 $W,S,P$，表示目的地位置，移动限制和虫洞的数目。之后 $P$ 行，每行两个整数 $B$ 和 $E$，表示一个虫洞。

输入文件的最后一行是一个整数 $0$，表示输入的结束。

Output Format

对于每组测试数据，在单独的一行内输出结果。

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

４
３

Hint

对于 $30\%$ 的数据，$W≤1000$。

对于 $100\%$ 的数据，$W≤10^9$，$2≤S≤6$，$1≤P≤40$，没有 $B = 0$ 或者 $B = W$ 的虫洞，输入数据保证目的地可达。