Problem Description

There is a grid with $H$ rows and $W$ columns. Let the cell at the $i$-th row and $j$-th column be called cell $(i,j)$.

Each cell contains one piece. Shou has removed $K$ pieces from the grid. The $i$-th removed piece was located at cell $(R_i, C_i)$.

Shou can now perform the following operation zero or more times:

• Select a piece and move it from its current cell to an adjacent cell. The destination cell may contain another piece. Two cells are considered adjacent if they share an edge.

Shou's goal is to have all pieces on the same cell. Find the minimum number of operations required for Shou to achieve this goal.

Input Format

The input is given from the standard input in the following format:

$H$ $W$ $K$ $R_1$ $C_1$ $R_2$ $C_2$ $\vdots$ $R_K$ $C_K$

Output Format

Output the minimum number of operations required to have all pieces on the same cell.

Sample Input and Output

Sample Input #1

2 3 3
1 2
2 1
2 2

Sample Output #1

3

Sample Input #2

5 5 10
2 2
2 5
1 3
2 4
2 3
1 5
2 1
1 4
1 2
1 1

Sample Output #2

28

Sample Input #3

100000 100000 0

Sample Output #3

500000000000000

Sample Input #4

2 2 3
1 2
2 1
2 2

Sample Output #4

0

Notes/Hints

Constraints

• $1 \leq H \leq 10^5$
• $1 \leq W \leq 10^5$
• $0 \leq K \leq \min(10^5, H \times W - 1)$
• $1 \leq R_i \leq H$
• $1 \leq C_i \leq W$
• $(R_i, C_i) \neq (R_j, C_j)$ ($i \neq j$)
• All input values are integers.

Sample Explanation 1

Before any operations, the pieces are located at cells $(1,1)$, $(1,3)$, and $(2,3)$. The following three operations will place all pieces on the same cell:
- Move the piece at cell $(1,1)$ to cell $(1,2)$.
- Move the piece at cell $(1,2)$ to cell $(1,3)$.
- Move the piece at cell $(2,3)$ to cell $(1,3)$.
It is not possible to achieve the goal with two or fewer operations, so the answer is $3$.

见题面 Input 部分

见题面 Output 部分