[HAOI2007] 覆盖问题

题目描述

某人在山上种了 $N$ 棵小树苗。冬天来了,温度急速下降,小树苗脆弱得不堪一击,于是树主人想用一些塑料薄膜把这些小树遮盖起来,经过一番长久的思考,他决定 用 $3$ 个 $L \times L$ 的正方形塑料薄膜将小树遮起来。我们不妨将山建立一个平面直角坐标系,设第 $i$ 棵小树的坐标为 $(X_i,Y_i)$ ,$3$ 个 $L \times L$ 的正方形的边要求平行于坐标轴,一个点如果在正方形的边界上,也算作被覆盖。当然,我们希望塑料薄膜面积越小越好,即求 $L$ 最小值。

输入输出格式

输入格式


接下来有 $N$ 行,第 $i+1$ 行有 $2$ 个整数 $X_i,Y_i$,表示第 $i$ 棵树的坐标,保证不会有 $2$ 个树的坐标相同。

输出格式


一行,输出最小的 $L$ 值。

输入输出样例

输入样例 #1

4
0 1
0 -1
1 0
-1 0

输出样例 #1

1

说明

对于 $100\%$ 的数据,$-1,000,000,000 \le X_i,Y_i \le 1,000,000,000。$ 对于 $30\%$ 的数据,$N \le 100。$ 对于 $50\%$ 的数据,$N \le 2000。$ 对于 $100\%$ 的数据,$N \le 20000。$