8099: BZOJ4099：[Usaco2015 Open]Trapped in the Haybales

Farmer John has received a shipment of N large hay bales (1≤N≤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 Sj and a position Pj 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. 农民约翰收到了N个干草包(1≤N≤100000)，并将它们放置在一条道路上的 不同位置。不幸的是，他忘记了贝西是沿着道路放牧，她现在可能被困在干 草包里了！  每个包有一个大小Sj和位置Pj。贝西可以沿着道路自由走动，甚至可以 到达一捆草包所在的位置，但她必须通过这个位置。如果她向同一方向跑D单 位的距离，她就可以突破大小严格小于D的干草包。当然，这样做后她就可以 开发出更广阔的空间，突破其他干草包。  如果贝西可以突破最左边或最右边的干草包，她就可以重获新生。请计 算贝西无法逃脱的道路的面积。 

输入格式

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…10^9. All positions are distinct. 输入的第一行包含一个整数N。以下N行每行描述一捆干草包，包含两个 整数，分别表示它的大小和位置，每个数的范围是1...10^9。所有的位置是不同 的。 

输出格式

Print a single integer, giving the area of the road from which Bessie cannot escape. 输出一个整数，表示贝西无法逃脱的道路面积。 

样例输入

5
8 1
1 4
8 8
7 15
4 20

样例输出

14

提示

没有写明提示

题目来源

Gold 感谢AaronPolaris提供译文