F. Alfred and Georg
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Mathematicians Alfred and Georg play a game. They take a white rectangular sheet of paper of size n × m divided into unit square cells. First, Alfred paints some of the cells black, and then Georg has to paint all the cells white again. To do that, Georg can perform the following operation an arbitrary number of times:

  • Put a pencil to the bottom left corner of the sheet (let us assume that this corner has coordinates (0, 0)), and draw a path to the top right corner of the sheet (that is, to the point with coordinates (n, m)). The path should go along the borders of the cells, and it is only allowed to move the pencil up or to the right. That is, if the pencil is located at coordinates (x, y) Georg is only allowed to move it to positions (x + 1, y) and (x, y + 1) and only if it will remain inside the sheet of paper or on its border.
  • Change the color of all cells that are located under the path (that is, repaint black all white cells under the path, and repaint white all black cells). After that, erase the drawn path, and (if necessary), proceed to the next operation.

While Georg is working, Alfred mentally tries to count the smallest number of operations needed to finish the game starting from the initial configuration. He asked you to write a program that would answer this question.

Input

The first line contains three integers n, m and k (1 ≤ n, m ≤ 500 000, 0 ≤ k ≤ 500 000) — the dimensions of the sheet, and the number of black cells respectively.

The subsequent k lines describe the black cells. The i-th of these lines contains two integers xi, yi — coordinates of the bottom left corner of the i-the black cell in the coordinate system described above (0 ≤ xi < n, 0 ≤ yi < m). It is guaranteed that all cells in the input are distinct.

Output

Print one number — the smallest number of operations needed to finish the game. If it is impossible to paint the whole sheet white, print  - 1.

Examples
Input
2 2 3
0 0
1 0
1 1
Output
1
Input
2 2 3
0 0
0 1
1 1
Output
2
Input
2 2 3
1 0
0 1
1 1
Output
3
Note

In first sample one path is enough: (0, 0) → (0, 1) → (1, 1) → (1, 2) → (2, 2).

In the second sample two paths are enough: (0, 0) → (1, 0) → (1, 1) → (2, 1) → (2, 2) and (0, 0) → (0, 2) → (2, 2).