测试数据来自 system/2262

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　在一条笔直的马路上，设置了 \(N\) 个障碍物，其中第 \(i\) 个障碍物的位置为 \(x_i\)，强度为 \(p_i\)。小精灵从一个没有障碍物的地方出发，它可以在这条马路上自由地走来走去，甚至走到某一个障碍物所在的位置，但它不能穿过那个点。

　　但有个例外，如果从某个位置朝着一个方向冲刺 \(D\) 个单位的距离，小精灵就可以积攒到足够的冲击力来冲跨一个强度小于 \(D\) 的障碍物。这之后，它可能开拓了更多的空间，在这个空间中，它又可以走到一个合适的位置，选择一个方向冲向其他的障碍物，并冲垮它们。如果小精灵最终突围了最左边或最右边的任意一个障碍物，它就逃脱了。

　　然而，从某些区间内的任何位置上出发，无论朝哪个方向冲刺，小精灵都无法逃脱出来，比如下图1中有3个障碍物，位置分别为 1,4,8，强度分别为8,1,8（红色数字表示）。小精灵站在第1个障碍物的地方向第2个障碍物冲刺，可以冲破这个障碍物。但图2中在位置1和位置8的障碍物之间，无论小精灵在这个区间中的哪个位置，都无法冲破这两个障碍物，无法逃脱。

　　现在请你小计算无法逃脱的位置区间长度是多少？比如说，如果小精灵的起始位置是在两个障碍物之间从 1 到 8 的位置上，而且在这中间小精灵无法逃脱，那么它无法逃脱的位置区间的长度就是 7。

【输入格式】

　　第一行包括数字 \(N\)，接下来的 \(N\) 行每行表示一个障碍物，包括两个整数，分别表示该障碍物的强度和位置。每个值在 \(1 .. 10^9\) 之间。

【输出格式】

　　输出一个整数，表示小精灵在这条路上无法逃脱的起始位置的区间长度。

【输入输出样例】

　Input

6
3 1
2 5
6 9
7 15
4 20
7 23

　Output

9

【输入输出样例解释】

　　样例输入的数据如下图所示（红色数字代表障碍物强度）：

　　◆第1个障碍物和第2个障碍物之间的区域[1,5]中，先走到障碍物2的坐标5处，向左冲刺，冲破障碍物1逃脱；或者先走到障碍物1的坐标1处，向右冲刺可以冲破障碍物2，接着再走到走到障碍物1的坐标1处，向右冲刺可以冲破障碍物3，……，直到可以冲破最右边的障碍物6逃脱。
　　◆第2个障碍物和第3个障碍物之间的区域[5,9]中，先走到障碍物3的坐标9处，向左冲刺，冲破障碍物2，接着再走到走到障碍物3的坐标9处，向左冲刺可以冲破障碍物1，逃脱；
　　◆第3个障碍物和第4个障碍物之间的区域[9,15]中，无论从哪个位置向哪个方向冲刺，都不能冲破两个障碍物，所以无法逃脱；
　　◆第4个障碍物和第5个障碍物之间的区域[15,20]中的任何点，先走到障碍物4的坐标15处，向右冲刺，冲破障碍物5逃脱；接着再走到走到障碍物4的坐标15处，向右冲刺可以冲破障碍物6，逃脱；
　　◆第5个障碍物和第6个障碍物之间的区域[20,23]中，无论从哪个位置向哪个方向冲刺，都不能冲破两个障碍物，所以无法逃脱；
　　所以无法逃脱的区域长度为(15-9)+(23-20)=9。

【数据限制】

　　对于 \(40\%\) 的数据，\(1≤N≤4000\)。
　　对于 \(100\%\) 的数据，\(1≤N≤100000\)。

【来源】

　　Mr.he