In such a game "Pirates!" the task of one of the players is to guide a merchant ship with a valuable cargo across the sea, on the islands of which the pirates are based.
The field is a rectangle consisting of square cells. The player can move to one of the four cells adjacent to the side in one move without leaving the field. The merchant ship starts its journey in any cell of the leftmost column and must enter any cell of the rightmost column of the playing field.
Pirate bases are located on the islands, which also occupy one square of the playing field, their location is known.
Vasya found out that the greater the distance from the pirate base, the safer the route. the distance is calculated as the number of moves in the cells from the pirate bases to each of the cells of the route.
Help him figure out the minimum distance he has to approach the pirate base by following the safest route.
Input data format
The first line contains natural numbers N and M (1 <= N, M <= 1,000,000) the number of rows and columns on the playing field.
The second line contains a natural number K (1 <= K <= 500) number of pirate bases.
The next K lines contain pairs of numbers Ri , Ci (1 <= Ri <= N, 1 <= C i <= M) coordinates of pirate bases (line, column).
Output format
Output one number the minimum distance that you will have to approach the pirate base on the safest route.
Rating system
Solutions that work correctly for N, M 6<=500 will score at least half of the points.
|
Enter |
Output |
10 10
4
2 2
5 3
5 9
8 8 |
3 |
Note
An example of one of the safe routes is shown in the figure. Pirate bases are marked in black, route cells in grey. The minimum distance from the pirate base to the route is 3 turns.
