题目描述

在一个大小为 $10^9 \times 10^9$ 的方格上，其中位于第 $a$ 行和第 $b$ 列的单元格表示为 $(a,b)$。

方格中一共有 $n$ 个怪物，其中第 $i$ 个怪物位于 $(x_i, y_i)$ 单元格中，其他单元格为空。一个格子中最多只能有一个怪物。

徐老师最多可以将一只怪物移动到另一个未被其他怪物占据的任何单元格。

在移动以后，他需要选择在这个方阵中选择一个矩形，要求所选矩形必须把所有的怪物都包含进来然后消灭，这个矩形中每个格子你都需要支付 $1$ 枚金币。

请问徐老师该如何移动一只怪物，才能让他消灭怪物所花费的金币数量最少。

输入格式

第一行包含一个整数 $n$，表示怪物的数量 。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ，表示第 $i$ 个怪物所在的单元格，所有（ $x_i, y_i$ ）都是不同的。

输出格式

输出消灭 $n$ 只怪物所需的最少金币数量。

样例数据

输入样例1

3
1 1
1 2
2 1

输出样例1

3

将第三只怪兽从 $(2,1)$ 移动到 $(1,3)$ 只需要花 $3$ 个金币。

输入样例2

5
1 2
4 2
4 3
3 1
3 2

输出样例2

6

将第一只怪兽从 $(1,2)$ 移动到 $(3,3)$ 只需要花 $6$ 个金币。

输入样例3

4
1 1
1 10
10 1
10 10

输出样例3

100

数据范围

对于 $20\%$ 的数据， $1 \le n \le 3$；

另有 $30\%$ 的数据，不用移动怪物，所花金币最少；

对于 $100\%$ 的数据， $1\le n \le 2 \times 10^5$，$1 \le x_i,y_i \le 10^9$。