Migrated from Lutece 3186 神奇王国（hard）

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

这是这道题的 hard version，与 easy version 的差别仅在于 $n$ 的范围。

ljy 来到了一个神奇的王国，在这里他获得了 $n$ 件神奇的物品。

这些物品的神奇之处在于任意一件物品处在不同的摆放状态下时可以呈现处两种不同的状态 $x$ 和 $y$。

更加神奇的地方在于，这 $n$ 件物品占据的空间采用以下方式计算：

假定 $v_i$ 代表第 $i$ 件物品所处的状态，对于所有不相等的 $i, j$，记 $w$ 为 $|v_i - v_j|$ 的最小值，$w$ 则为这 $n$ 件物品在当前状态下需要的空间。

由于 ljy 总是喜欢把东西以任意形式的塞进他的背包里，所以他想要知道至少需要一个多大的背包才能保证装下这 $n$ 件物品。

Input

第一行输入一个整数 $n$。

接下来 $n$ 行，每行两个整数 $x_i, y_i$，代表的一个物品的两种状态。

Output

输出一行一个整数，代表 ljy 至少需要一个多大的背包。

Samples

3
1 3
2 5
1 9

4

5
2 2
2 2
2 2
2 2
2 2

0

Constraints

$2\le n\le 10^4$

$1\le x_i, y_i\le 1\times10^9$

Resources

2024 UESTC ICPC Training for Graph