Trapped in the Haybales (Gold)#11175
Farmer John has received a shipment of large hay bales and placed them at various locations along the road leading to his barn. Unfortunately, he completely forgot that Bessie the cow is grazing along the road, and she may now be trapped among the hay bales!
Each bale has a size s_j and a position p_j, specifying its location along the one-dimensional road. Bessie can move freely along the road, including up to the position occupied by a bale, but she cannot pass through a bale.
There is one exception: if Bessie runs in the same direction for units of distance, she builds up enough speed to break through and permanently eliminate any hay bale whose size is strictly less than . Of course, after breaking through a bale, she may open up additional space, allowing her to make another run at other hay bales and eliminate them as well.
Bessie can escape to freedom if she can eventually break through either the leftmost or the rightmost hay bale. Please compute the total length of the road consisting of all real-valued starting positions from which Bessie cannot escape.
The first line contains an integer n~(1 \le n \le 10^5). Each of the next lines describes a hay bale and contains two integers representing its size and position, each in the range 1 \ldots 10^9. All positions are distinct.
Print one integer representing the total length of the road from which Bessie cannot escape.
Beispiel 1