Problem4140--USACO 2015 US Open, Bronze Problem 3. Trapped in the Haybales

4140: USACO 2015 US Open, Bronze Problem 3. Trapped in the Haybales

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

Farmer John has received a shipment of NN large hay bales (1≤N≤40001≤N≤4000) 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 jj has a size SjSj and a distinct position PjPj giving its location along the one-dimensional road. Bessie the cow starts at some location where there is no hay bale, and 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 DD units of distance, she builds up enough speed to break through and permanently eliminate any hay bale of size strictly less than DD. 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. For example, if Bessie cannot escape if she starts between hay bales at positions 1 and 5, then these encompass an area of size 4 from which she cannot escape.


Input

INPUT FORMAT (file trapped.in):

The first line of input contains NN. Each of the next NN lines describes a bale, and contains two integers giving its size and position, each in the range 1…1091…109.


Output

OUTPUT FORMAT (file trapped.out):

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


Sample Input Copy

SAMPLE INPUT:
5
8 1
1 4
8 8
7 15
4 20

Sample Output Copy

SAMPLE OUTPUT:
14

Source/Category