P5098 [USACO04OPEN] Cave Cows 3

题目描述

约翰的 $N$（$1 \leq N \leq 50000$）只牛在一个黑魃魃的洞里探险，他们只能通过叫声交流。

两只牛之间的曼哈顿距离决定了声音传播的时间。即牛一与牛二交流，需要的时间为 $|x_1-x_2|+|y_1-y_2|$。其中 $-10^6 \leq x_1,x_2,y_1,y_2 \leq 10^6$。

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

5
1 1
3 5
2 7
8 1
4 4

输出 #1

12

说明/提示

样例解释：

$(2,7)$ 和 $(8,1)$ 两点间的距离最大，为 $12$。