#1484. 「HCOI-R1」孤独的 sxz

「HCOI-R1」孤独的 sxz

题目描述

食堂的座位可以看成一个被划分为 n×mn\times m 的格子的矩形,长为 nn,宽为 mm,矩形内的每一个格子 (i,j)(i∈[1,n],j∈[1,m])(i, j)(i \in [1, n], j \in [1, m]) (i,j(i,j 为整数)) 都是一个座位。

现在,食堂里已经有了 kk 个人,其中第 i(1≤i≤k)i(1 \leq i \leq k) 个人坐在 (xi,yi)(x_i, y_i) 处。sxz 想要找到一个座位,使得该座位与 kk 个人的曼哈顿距离之和最大。请你帮他找到这个最大值,剩下的就交给 sxz 吧!

假设 sxz 坐在点 (a,b)(a,b),那么他和 kk 个人的曼哈顿距离之和是 ∑i=1k∣a−xi∣+∣b−yi∣\sum_{i=1}^{k}|a-x_i|+|b-y_i|。

很显然,sxz 不能和 k\bm k 个人中的任何一个人坐在同一个地方。

输入格式

第一行包含三个整数 n,m,kn, m, k。

接下来 kk 行,第 ii 行两个整数描述 xi,yix_i, y_i。

输出格式

仅一行一个整数,描述这个值。注意它可能很大。

样例

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

题目来源:洛谷 P10025