题目描述

草原上着火了！

有 $n$ 个着火点 ，为了研究火的蔓延情况，模型简化如下：

草原可以视为一个二维平面，初始（第 $0$ 秒）有若干着火点，一个着火点每过 $1$ 秒就会向 $4$ 个方向扩散一个距离。

即，若当前 $(x,y)$ 为着火点，那么下一秒 $(x - 1,y),(x+1,y),(x,y - 1),(x,y + 1)$ 中不是着火点的点都会变成着火点。

一片着火区域指区域内的所有点都为着火点，且任意一个着火点都可以通过相邻的着火点到达所有的其他着火点。

点 $(x_0,y_0)$ 的相邻点 $(x,y)$ 定义为与其曼哈顿距离为 $1$ 的点。

曼哈顿距离：二维平面中点 $(x,y)$ 和点 $(x_0,y_0)$ 的曼哈顿距离为 $|x - x_0| + |y - y_0|$。

假设一开始只有 $(0,0)$ 为着火点，那么着火点的扩散如图所示：

给定平面上的 $n$ 个着火点，问最早什么时候形成一个着火区域。

输入格式

第一行一个数 $n$ ，以下 $n$ 行，每行一个点坐标。

输出格式

输出仅一个数，表示最早的时刻所有着火点形成着火区域。

1
0 1000000000

0

2
0 0
1 4

2

数据规模与约定

下发文件

下发文件分别对应子任务 $1,4$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 10^3,0 \leq x_i,y_i \leq 10^{9}$。