P10025 "HCOI-R1" Lonely sxz

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.

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.**

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

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

### 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