题目描述

小蓝和小红在玩一个游戏，这个游戏在数轴上面展开。数轴的概念如下:

数轴是一种用来表示实数的图形工具。它通常是一条直线，上面标有一系列的数值点，这些点代表实数。数轴的中心通常是0，而且向右边递增的方向表示正数，向左边递减的方向表示负数。

数轴上的每个点都与一个实数相对应，而且相邻的两个点之间的距离是相等的，通常表示为单位距离。这样的设计使得数轴可以清晰地展示实数之间的大小关系，包括正数、负数和零。

这个游戏的流程如下：

1. 首先由小蓝和小红两人在数轴上确定$n$条线段$segment_i$，线段可以重叠。然后再选取一个随机数$k$。
2. 接着由小蓝先手，小红后手，从数轴坐标$0$开始起跳，每次可以跳不超过$k$个单位。也就是说加入当前位置是$pos$，那么可以跳跃的范围为$[pos-k,pos+k]$。
3. 每位玩家必须在第$i$-th跳跃后，必须恰好落在$segment_i$中，也就是说假如$segment_i$的左端点和右端点为$l_i$和$r_i$，那么落点$pos$需要满足$l_i\le pos\le r_i$。
4. 最后在$segment_n$谁跳跃的总距离小获胜。

但是经过多次游戏后，聪明的小蓝发现这个游戏不是对于任意的一个$k$都能满足的，有的时候$k$的取值不对，导致游戏没法顺利进行，因此需要确定一个$k$的随机选取的区间，很显然$k$在很大的时候是都可以的，但是$k$的最小取值是多少呢？聪明的小蓝希望更聪明的你能够帮他解答这个问题。

输入格式

第一行一个正整数$n$代表线段的数量。
第二行$n$对正整数$l_i，r_i$代表$segment_i$

输出格式

一个正整数$k$，代表$k$的最小值

样例输入输出

5
1 2
1 6
9 12
4 7
5 17

4

解释

第一步可以跳跃2，坐标变换为：$0->2$
第二步可以跳跃4，坐标变换为：$2->6$
第三步可以跳跃3，坐标变换为：$6->9$
第四步可以跳跃2，坐标变换为：$9->7$
第五步可以跳跃0，坐标变换为：$7->7$
可以证明无法选取更小的$k$使得游戏可以正常进行。

数据范围

$1\le n \le 5\times10^5，0\le l_i,r_i \le 10^{12}$