I. Pace Pushers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

On a straight training track, coaches drop effort beacons. Each beacon projects an intensity zone. Whenever zones overlap and one is weaker, the weaker beacon levels up by one. All beacons update together each round until the effort levels stop changing.

You are given an integer $$$N$$$ ($$$1 \le N \le 2 \cdot 10^{5}$$$). There are $$$N$$$ beacons on a straight line. For each $$$i$$$, you are given a position $$$x_i$$$ ($$$0 \le x_i \le 10^{9}$$$) and a power $$$p_i$$$ ($$$1 \le p_i \le 10^{9}$$$).

Each beacon $$$i$$$ powers the closed interval $$$[\,x_i - p_i,\; x_i + p_i\,]$$$.

If two powered intervals overlap and their powers are not equal, the weaker beacon's power increases by $$$1$$$. All such increases happen synchronously in rounds: in each round, every beacon decides using the powers at the start of that round, and all chosen increases occur together. Repeat rounds until a full round makes no changes (it can be shown that this process terminates). In the final state, output the total length covered by the union of all powered intervals.

The length of the interval $$$[l, r]$$$ is calculated as $$$r - l + 1$$$.

Input

The first line contains $$$N$$$. Each of the next $$$N$$$ lines contains two integers, $$$x_i$$$ and $$$p_i$$$.

Output

Print a single integer — the length of the union of the intervals in the final (stable) state.

Example
Input
7
0 1
3 1
5 2
9 1
12 3
20 1
21 1
Output
23
Note

Intervals are inclusive, and updates are synchronous. For the input above the initial intervals are $$$[-1,1],[2,4],[3,7],[8,10],[9,15],[19,21],[20,22]$$$ and $$$p=(1,1,2,1,3,1,1)$$$.

Overlaps force weaker beacons to level up: first $$$2$$$ and $$$4$$$, then the increase cascades through beacons $$$1$$$ to $$$5$$$ . After $$$5$$$ rounds, beacons $$$1$$$ to $$$5$$$ equalize at power $$$3$$$ while $$$6$$$ and $$$7$$$ stay at $$$1$$$, so the final components are $$$[-3,15]$$$ and $$$[19,22]$$$. The total inclusive length is $$$(15-(-3)+1)+(22-19+1)=19+4=23$$$.