Trapped in the Hay Bales

Farmer John has received a shipment of N large hay bales, each with a size (S_j) and located at position (P_j) along a one-dimensional road. Bessie the cow is out grazing on the road and might be trapped between these bales. Bessie can move freely along the road up to the position at which a bale is located – she cannot cross that position. However, if she runs continuously in one direction for a distance (D), she gains enough momentum to break through (and permanently remove) any hay bale whose size is strictly less than (D).

After breaking a bale, previously blocked paths might open up, allowing her to build further momentum and eliminate additional hay bales. Bessie escapes to freedom if she is able to eventually break through either the leftmost or rightmost hay bale.

Your task is to compute the total length (area) of the road – i.e. the set of real starting positions along the road (between the extreme hay bales) – from which Bessie cannot escape.

inputFormat

The first line contains an integer (N) ( (1 \leq N \leq 100{,}000)), the number of hay bales. Each of the next (N) lines contains two integers (P_j) and (S_j), where (P_j) is the position of the bale and (S_j) is its size. The hay bales may be given in arbitrary order. It is guaranteed that all positions are distinct.

outputFormat

Output a single integer or real number: the total length of the road (within the interval from the leftmost bale to the rightmost bale) consisting of starting positions from which Bessie cannot escape.

sample

3
1 2
3 1
6 3

0