AT_abc419_c [ABC419C] King's Summit

有一个 $10^9$ 行 $10^9$ 列的网格。记 $(i, j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。 网格上有 $N$ 个人。初始时，第 $i$ 个人在格子 $(R_i, C_i)$。 时间从 $0$ 开始。每个人可以在时间 $1, 2, 3, 4, \ldots$ 时进行如下操作： - 保持当前位置不动，或者移动到 $8$ 邻接的格子。禁止离开网格。具体来说，若当前位置为 $(i, j)$，则可以移动到存在的 $(i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1)$ 之一。假设移动不耗时。 请你求出 $N$ 个人能够汇聚到同一个格子的最小时间。

输入从标准输入读入，格式如下： > $N$ > $R_1\ C_1$ > $R_2\ C_2$ > $\vdots$ > $R_N\ C_N$

输出答案。

### 样例解释 1 如果每个人按如下方式移动，则所有人可以在时间 $3$ 时汇聚到格子 $(5, 4)$。 - 时间 $1$：第 1 个人移动到 $(3, 4)$，第 2 个人移动到 $(6, 2)$，第 3 个人移动到 $(7, 2)$。 - 时间 $2$：第 1 个人移动到 $(4, 4)$，第 2 个人移动到 $(5, 3)$，第 3 个人移动到 $(6, 3)$。 - 时间 $3$：第 1、2、3 个人都移动到 $(5, 4)$。 ### 样例解释 2 所有人一开始就在同一个格子。 ### 数据范围 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq R_i, C_i \leq 10^9$ - 所有输入值均为整数。 由 ChatGPT 4.1 翻译