题目描述

大城市的道路是相互平行或垂直的，如果在城市的道路上行走，不能用点与点之间的直线距离计算长度，而是应该定义两个点（设坐标分别为 (x,y) 与 (x′,y′)）的城市距离为 ∣x−x′∣+∣y−y′∣

给定 n 个点的坐标，请从中寻找两个点，使得它们的城市距离达到最大，并输出这个最大值。

输入格式

第一行：单个整数 n。 第二行到第 n+1 行：每行有两个整数 xi 和 yI，表示一个点的坐标。

输出格式

单个整数：表示最大的城市距离。

数据范围

• 对于 30% 的数据，2≤n≤5,000；
• 对于 60% 的数据，2≤n≤50,000；
• 对于 100% 的数据，2≤n≤500,000。
• −500,000,000≤xi​,yi​≤500,000,000；

样例数据

输入:

4
0 0
0 1
1 3
3 2

输出:

5

说明:

(0,0)与(3,2)的城市距离是最大的