#3382. [Usaco2004 Open]Cave Cows 3 洞穴里的牛之三

题目描述

约翰的N(1≤N≤50000)只牛在一个黑魃魃的洞里探险．他们只能通过叫声交流．

两只牛之间的曼哈顿距离决定了声音传播的时间．牛1与牛2交流，需要的时间为

|x1-x2|+|y1-y2|

其中x,y∈[_10^6，10^6]．

那任意一对牛之间交流时间的最大值为多少？

输入格式

第1行输入N，接下来每行输入一只牛的坐标

输出格式

交流时间最大值（即最大曼哈顿距离）．

样例

样例输入

5  

1 1  

3 5  

2 7  

8 1  

4 4

样例输出

12

数据范围与提示

(2，7)和(1，8)之间的曼哈顿距离为12