Given an $N \times M$ grid graph with 4-connectivity. There are $Q$ people, where the $i$-th person is initially located at $(X_i, Y_i)$. You need to plan a path for each person to reach the boundary (the first row, the last row, the first column, or the last column) such that no two paths intersect at any grid cell.

Determine if a solution exists. If it does, find the minimum possible sum of the path lengths for all people.

Input

The input contains multiple test cases.

The first line of each test case contains three integers $N, M, Q$.

The next $Q$ lines each contain two integers $X, Y$, describing the coordinates of each person.

Output

For each test case:

• If no valid solution exists, output -1.
• Otherwise, output a single integer representing the minimum sum of the path lengths for all people.

Examples

Input 1

4 4 2
2 3
3 3
5 5 3
2 3
2 4
3 2
6 6 5
2 3
3 2
3 3
3 4
4 3

Output 1

2
3
-1

Subtasks

For $70\%$ of the data, $1 \leq N, M \leq 200$.

For $100\%$ of the data, $1 \leq N, M \leq 2\,000$, $1 \leq NM \leq 200\,000$.

Note

1. The number of test cases was not provided during the contest; "please evaluate for yourself."
2. No memory limit was provided during the contest; it is set to 1 GB on QOJ.