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

时间限制:1s      空间限制:128MB

题目描述

    约翰的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

提示

   (27)(18)之间的曼哈顿距离为12


题目来源

Orange

Menuappsclose