Farmer John received a load of N large haystacks (1≤N≤4000) and placed the haystacks at various points along the road leading to his barn. Unfortunately, he completely forgot that Besi grazes along this road and may be trapped in these haystacks.
Each stack numbered j has a size Sj and a unique position Pj that specifies its position along the 1D road. Beshi starts at some position where there was no haystack and can move freely along the road up to the position where the haystack is placed, but she cannot cross that position. As an exception, if it is moving in some direction of D distance units, it gains enough speed to ram any haystack with a height strictly less than D. Of course, after she does this, an area opens up in front of her with other haystacks, which she can also ram.
Besi can go free after the leftmost haystack as well as after the rightmost haystack. Please determine the total length of the road, consisting of those positions from which Besi will not be able to get out. For example, if Besi can't get out if she starts in a position between the stacks at positions 1 and 5, then the answer is 4 (because those positions limit an area of size 4).
INPUT FORMAT:
The first line of input contains NN. Each of the following NN lines describes the stack and contains two integers specifying its size and position, each in the range 1…109.
OUTPUT FORMAT:
Output an integer specifying the length of the part of the road that Besi can't escape from.
| Input |
Output |
|
5
8 1
1 4
8 8
7 15
4 20
|
14 |