题目描述

定义两个点坐标分别为$(x, y)$与$(x', y')$时，它们的城市距离为$\vert x - x'\vert + \vert y - y'\vert$。给定$n$个点的坐标，需要从这些点中找出两个点，使得它们之间的城市距离达到最大值，并输出该最大值。

输入格式

• 第一行：一个整数$n$，表示点的数量。
• 第二行到第$n + 1$行：每行包含两个整数$x_i$和$y_i$，表示第$i$个点的坐标。

输出格式

一个整数，即所有点对中城市距离的最大值。

数据范围

• 对于30%的数据，$2 \leq n \leq 5000$。
• 对于60%的数据，$2 \leq n \leq 50000$。
• 对于100%的数据，$2 \leq n \leq 500000$，且$-500000000 \leq x_i, y_i \leq 500000000$ 。

样例数据

• 输入

4
0 0
0 1
1 3
3 2

• 输出

5

• 说明：点$(0, 0)$与$(3, 2)$之间的城市距离是所有点对中最大的。