题目描述

约翰的 $N$ 只牛在一个黑魃魃的洞里探险，他们只能通过叫声交流。两只牛之间的曼哈顿距离决定了声音传播的时间。牛 1 与牛 2 交流，需要的时间为 $|x_1 - x_2| + |y_1 - y_2|$。

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

输入格式

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

输出格式

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

5
1 1
3 5
2 7
8 1
4 4

12

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

数据范围与约定

对于 $100\%$ 的数据，$1 ≤ N ≤ 50000$，$x, y \in [-10^6, 10^6]$。

题目来源

Orange