Farmer John received a load of N large stacks of hay (1≤N≤100,000) and laid them out in various positions along the road leading to the barn. Unfortunately, he completely forgot that Besi the cow grazes along the road and can get trapped between the haystacks.
Each j stack has a size of Sj and a position of Pj defining its position along the road. Besi can move along the road up to the haystack position, but cannot cross that position. Exception – if it traveled in that direction in D units of distance, then it gained enough speed to ram through a haystack of any size strictly less than D< /strong>. Of course, after that, she can continue moving and ram other haystacks.
Besi can go free if she eventually rams the leftmost or rightmost haystack. Calculate the total size of the section of the road, consisting of possible starting points for Besi, from which she cannot escape.
WATER FORMAT:
The first input line contains N. Each of the following N lines describes the stack, and contains two integers specifying the size and position in the range 1…109. All positions are different.
OUTPUT FORMAT:
Print a single integer – the size of the area of the road Besi can't get out of.
|
Enter |
Output |
|
5
8 1
14
8 8
7 15
4 20
|
14 |