Description

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

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

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

Format

Input

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

Output

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

Samples

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

5

Limitation

100%的数据：1<=n<=20000;-1000000000<=xi,yi<=1000000000;