题目背景

applepi 想进行宇宙旅行。当然，applepi 知道这是有可能的，因为 applepi 的特殊能力能使他观测到宇宙中的虫洞。所谓虫洞就是一个在三维之外的维度打开的快捷通道，通过虫洞能够从一个地方瞬间移动到另外一个地方。

题目描述

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

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

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

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

输入格式

输入包含多组测试数据。

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

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

输出格式

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

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

４
３

提示

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

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