曼哈顿距离

题目描述

在二维平面上有 $N$ 个点,第 $i$ 个点的坐标是 $(x_i,y_i)$。 同一个坐标上可能有多个点。 两个不同点之间的曼哈顿距离的最大可能值是多少?

其中,两点 $(x_i,y_i)$ 和 $(x_j,y_j)$ 的曼哈顿距离指 $|x_i-x_j|+|y_i-y_j|$。

输入格式

输入按以下格式从标准输入给出:

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$:$
$x_N$ $y_N$

输出格式

输出答案。

样例

3
1 1
2 4
3 2

4

第 $1$ 个点和第 $2$ 个点的曼哈顿距离是 $|1-2|+|1-4|=4$,这是最大值。

2
1 1
1 1

0

数据范围

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq x_i,y_i \leq 10^9$
• 输入均为整数