题目描述

Alice 和 Bob 是朋友，他们有 N 个点 (X_i, Y_i)，平时经常拿这些点来做游戏。可惜最近两人都很忙，没法一起玩了，于是他们决定把这些点划分成两个集合：

• A 交给 Alice；
• B 交给 Bob；

并且两个人都必须至少得到一个点。

Alice 不喜欢“太宽”的集合，而 Bob 不喜欢“太高”的集合。这里定义：

• 一个集合的宽度，是其中最右点与最左点的横坐标之差；
• 一个集合的高度，是其中最高点与最低点的纵坐标之差。

两人希望最小化：

• 集合 A 的宽度；
• 加上集合 B 的高度。

由于点很多，他们不容易自己找到最优划分方案。请你编写程序 sets，求出这个最小可能值。

输入格式

第一行输入一个整数 N，表示点的个数。
接下来 N 行，每行输入两个整数 X_i 和 Y_i，表示第 i 个点的坐标。

为方便起见，输入保证点按 X 非降序给出，即：

X_i <= X_{i+1}

输出格式

输出一行一个非负整数，表示所求最小值。

数据范围

2 <= N <= 2 × 10^6
0 <= X_i, Y_i <= 10^8

子任务

样例 1

输入 1

11
1 28
5 24
11 14
13 43
19 29
23 6
28 25
36 51
39 32
44 29
50 21

输出 1

36

样例解释 1

一种最优划分方案是：将编号为 2, 3, 5, 7, 8 的点放入 A，其余点放入 B（这里编号按 0 到 N-1 计）。

此时：

• A 的宽度为 39 - 11 = 28；
• B 的高度为 29 - 21 = 8。

所以答案为：

28 + 8 = 36