Background

sxz is not good at socializing, so he usually likes to sit in secluded places. Today, sxz came to the cafeteria. He still wants to find a secluded seat, making the sum of Manhattan distances from him to all other people as large as possible.

Problem Description

The seats in the cafeteria can be seen as a rectangle divided into an $n \times m$ grid, with length $n$ and width $m$. Each cell $(i, j)$ $(i \in [1, n], j \in [1, m])$ ($i, j$ are integers) is a seat.

Now there are already $k$ people in the cafeteria. The $i$-th person $(1 \leq i \leq k)$ sits at $(x_i, y_i)$. sxz wants to find a seat such that the sum of Manhattan distances from this seat to the $k$ people is maximized. Please help him find this maximum value, and leave the rest to sxz.

Suppose sxz sits at point $(a, b)$. Then the sum of Manhattan distances between him and the $k$ people is $\sum_{i=1}^{k}|a-x_i|+|b-y_i|$.

Obviously, sxz cannot sit at the same position as any of the $\bm k$ people.

Input Format

The first line contains three integers $n, m, k$.

The next $k$ lines: the $i$-th line contains two integers $x_i, y_i$.

Output Format

Only one line with one integer, describing this value. Note that it may be very large.

2 5 3
1 1
1 3
1 4

10

7 4 9
1 4
2 3
4 1
6 2
7 1
5 2
3 4
1 1
7 4

38

Hint

Sample Explanation 1

The best position is $(2, 5)$. The Manhattan distances to the $3$ people are $5$, $3$, and $2$, respectively.

Constraints

This problem uses bundled testdata.

• Subtask 0 (15 pts): $n, m \leq 100$.
• Subtask 1 (25 pts): $n, m \leq 10000$.
• Subtask 2 (20 pts): $k = 3$.
• Subtask 3 (40 pts): No special constraints.

For all data, $1 \leq n, m \leq 10^9$, $1 \leq k \leq \min\{4 \times 10^5, n \times m - 1\}$, $1 \leq x_i \leq n$, $1 \leq y_i \leq m$, and it is guaranteed that all $(x_i, y_i)$ are pairwise distinct.

Translated by ChatGPT 5