Minimum Time to Reach Destination

We consider a one-dimensional coordinate system. The Earth is located at \(0\) while applepi's destination is at a positive integer \(W\). In each unit time, applepi can move an integer distance from \(1\) to \(S\) in the positive direction. Furthermore, wormholes are given as tuples \((B, E)\). When applepi finishes a move exactly at position \(B\), he is immediately teleported to position \(E\). Note that if applepi merely passes through \(B\) during his move, he will not be teleported. Also, applepi is not allowed to move in the negative direction by his own move (but wormhole teleportation may go in any direction). Your task is to compute the minimum number of unit time steps required for applepi to reach his destination \(W\).

Input Format: The first line contains three integers: \(W\), \(S\) and \(N\) (the number of wormholes). Each of the following \(N\) lines contains two integers representing a wormhole: \(B\) and \(E\).

Output Format: Output a single integer representing the minimum number of unit time steps needed to reach \(W\). It is guaranteed that a solution exists.

inputFormat

The first line contains three integers \(W\), \(S\), \(N\), where \(W (\geq 1)\) is the destination, \(S (\geq 1)\) is the maximum integer steps allowed per move, and \(N (\geq 0)\) is the number of wormholes. The next \(N\) lines each contain two integers \(B\) and \(E\) denoting a wormhole. When applepi lands exactly on \(B\), he is teleported to \(E\).

outputFormat

Output a single integer indicating the minimum number of time units required for applepi to reach position \(W\).

sample

10 3 1
3 8

2