{"problem":{"name":"「HCOI-R1」孤独的 sxz","description":{"content":"食堂的座位可以看成一个被划分为 $n\\times m$ 的格子的矩形，长为 $n$，宽为 $m$，矩形内的每一个格子 $(i, j)(i \\in [1, n], j \\in [1, m])$ $(i,j$ 为整数$)$ 都是一个座位。 现在，食堂里已经有了 $k$ 个人，其中第 $i(1 \\leq i \\leq k)$ 个人坐在 $(x_i, y_i)$ 处。sxz 想要找到一个座位，使得该座位","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10025"},"statements":[{"statement_type":"Markdown","content":"食堂的座位可以看成一个被划分为 $n\\times m$ 的格子的矩形，长为 $n$，宽为 $m$，矩形内的每一个格子 $(i, j)(i \\in [1, n], j \\in [1, m])$ $(i,j$ 为整数$)$ 都是一个座位。\n\n现在，食堂里已经有了 $k$ 个人，其中第 $i(1 \\leq i \\leq k)$ 个人坐在 $(x_i, y_i)$ 处。sxz 想要找到一个座位，使得该座位与 $k$ 个人的曼哈顿距离之和最大。请你帮他找到这个最大值，剩下的就交给 sxz 吧！\n\n假设 sxz 坐在点 $(a,b)$，那么他和 $k$ 个人的曼哈顿距离之和是 $\\sum_{i=1}^{k}|a-x_i|+|b-y_i|$。\n\n**很显然，sxz 不能和 $\\bm k$ 个人中的任何一个人坐在同一个地方**。\n\n## Input\n\n第一行包含三个整数 $n, m, k$。\n\n接下来 $k$ 行，第 $i$ 行两个整数描述 $x_i, y_i$。\n\n## Output\n\n仅一行一个整数，描述这个值。注意它可能很大。\n\n[samples]\n\n## Background\n\nsxz 不擅长与人交往，于是他平常都喜欢找偏僻的地方坐着。今天，sxz 来到了食堂，他依旧想找一个偏僻的地方坐着，让他与其他所有人的曼哈顿距离之和最大。\n\n## Note\n\n### 样例解释 1\n\n最佳位置为 $(2,5)$，对于 $3$ 个人的曼哈顿距离分别为 $5, 3, 2$。\n\n### 数据规模与约定\n\n**本题采用捆绑测试。**\n+ Subtask 0（15 pts）：$n, m \\leq 100$。\n+ Subtask 1（25 pts）：$n, m \\leq 10000$。\n+ Subtask 2（20 pts）：$k = 3$。\n+ Subtask 3（40 pts）：无特殊限制。\n\n对于所有数据，$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$，保证所有 $(x_i, y_i)$ 互不相同。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10025","tags":["洛谷原创","O2优化","洛谷月赛"],"sample_group":[["2 5 3\n1 1\n1 3\n1 4","10"],["7 4 9\n1 4\n2 3\n4 1\n6 2\n7 1\n5 2\n3 4\n1 1\n7 4","38"]],"created_at":"2026-03-03 11:09:25"}}