题目描述

看过隋唐演义的都知道“宇文成都”是天下第二武功高手，就在隋炀帝杨广被奸臣宇文化及（也就是宇文成都的父亲）所逼死，宫中一片大乱，然“宇文成都”是一代豪杰，不愿通过这种方式来取得皇位，于是只身一人与上万瓦岗起义军决战，以死报国（可惜啊，这么好的一个人，跟错了主）。

宇文成都只身一人击退起义军多位大将，就在这时，徐茂公准备下令让所有士兵冲上去活捉宇文成都，然而宇文成都已经发现，他甚至记住了所有士兵的位置（在平面直角坐标系上的坐标，均为整数），他现在可以使用师傅传授的武功，将一个长度为 $L$ 的正方形（平行于坐标轴，顶点坐标为整数）区域全部化为灰烬，$L$ 正比与他所消耗的功力，然而因为刚才运力过多，他现在只能使用 $3$ 次武功，每一次的攻击正方形边长 $L$ 都相同，三次使用武功后，他的体力总损耗为 $L$，每一次选择的正方形区域可以不同，也可以相交。现在他要把所有的 $n$ 个士兵全部消灭，请问他最少要消耗多少体力（即最小正方形边长）？

（每次使用武功可将正方形内部的士兵全部消灭，边界上也算）

输入格式

第一行一个整数 $n$（$n$ 个士兵）。
接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示每个士兵的坐标。

输出格式

共一行，一个整数，表示最小的体力消耗。

10
10 3
4 8
9 1
1 6
5 5
9 6
6 7
7 8
2 1
9 7

5

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^4$，$-10^9 \le x_i,y_i \le 10^9$。

此题存在版权，故原 BZOJ 不再支持提交，保留在此只供大家参考题面！ 望见谅！