题目描述

Farmer John has received a shipment of N large hay bales ($1 \le N \le 100,000$), and placed them at various locations along the road leading to his barn. Unfortunately, he completely forgets that Bessie the cow is out grazing along the road, and she may now be trapped within the bales! Each bale $j$ has a size $S_j$ and a position $P_j$ giving its location along the one-dimensional road. Bessie the cow can move around freely along the road, even up to the position at which a bale is located, but she cannot cross through this position. As an exception, if she runs in the same direction for $D$ units of distance, she builds up enough speed to break through and permanently eliminate any hay bale of size strictly less than $D$. Of course, after doing this, she might open up more space to allow her to make a run at other hay bales, eliminating them as well.

Bessie can escape to freedom if she can eventually break through either the leftmost or rightmost hay bale. Please compute the total area of the road consisting of real-valued starting positions from which Bessie cannot escape.

输入格式

The first line of input contains $N$. Each of the next $N$ lines describes a

bale, and contains two integers giving its size and position, each in the range

$1\ldots 10^9$. All positions are distinct.

输出格式

Print a single integer, giving the area of the road from which Bessie cannot

escape.

题目大意

题目描述

农夫约翰最近买了N个干草堆，他把这些干草堆都放在家和农场之间的一条直路上，每个干草堆的位置各不相同。不幸的是，他忘记了他的奶牛贝里斯正外出吃草，贝里斯也许会被这些干草堆所限制住！干草堆j的大小是Sj，在Pj的位置上。贝里斯从一个不是干草堆的地方出发，他可以自由的在这条直线上移动，他不能越过干草堆。有一种特殊的情况， 他可以往一个方向连续跑了D的距离以后，他就可以积累足够的能量，然后就可以消除小于D的干草堆。当然了，在消除了一个干草堆以后，他就可以有更多的空间来跑步和积蓄能量了。当贝里斯成功消除了第一个或者最后一个干草堆的时候，他就可以获得自由了，请你计算使得贝里斯不能获得自由的初始位置的区间总和。

输入

第一行是一个正整数N，表示干草堆的数量。接下来N行，每行两个正整数，分别表示干草堆的大小和位置。

输出

输出使得贝里斯不能获得自由的初始位置的区间总和。

感谢@sxyugao 提供的翻译

5
8 1
1 4
8 8
7 15
4 20

14