Trapped in the Haybales

Time limit1sMemory limit256 MB

Summary

The solver sorts bales by position, expands each gap while a neighbor is smaller than the open width, and sums the widths that never reach an end.

Level: Medium6 of 10
Topics: Two pointers, Sorting, Greedy
Solved: No attempts yet

Problem

Farmer John received $N$ large hay bales ( $1 \le N \le 4000$ ) and put them at various points along the road that leads to his barn. He forgot that Bessie the cow was grazing on that road, and she may now be trapped between the bales.

The road is a straight line. Bale $j$ has size $S_j$ and position $P_j$ , and all positions are distinct.

Bessie starts at some point where there is no bale and moves freely along the road. She can walk right up to the position of a bale, but she cannot pass through it. If she runs in one direction for a distance of $D$ , she builds up enough speed to smash one bale of size strictly less than $D$ and remove it for good. Removing a bale opens up more room to run, so she may then smash further bales.

Bessie escapes if she smashes either the leftmost bale or the rightmost bale. A start to the left of the leftmost bale, or to the right of the rightmost bale, always escapes, because she can run as far as she wants.

Compute the total length of road made up of the starting points from which Bessie cannot escape. Starting positions are real numbers. For example, if she cannot escape when she starts between bales at positions $1$ and $5$ , that stretch has length $4$ .

Input

The first line contains $N$ . Each of the next $N$ lines contains the size and the position of one bale, separated by a space. Both values are integers between $1$ and $10^9$ , and the positions are distinct.

Output

Print a single integer, the total length of road from which Bessie cannot escape.

Examples5

Example 1
Input
```
5
8 1
1 4
8 8
7 15
4 20
```
Expected output
```
14
```
Example 2
Input
```
1
1000000000 1000000000
```
Expected output
```
0
```
Example 3
Input
```
2
1 1
1 5
```
Expected output
```
0
```
Example 4
Input
```
2
10 1
10 5
```
Expected output
```
4
```
Example 5
Input
```
6
2 10
1000 1
5 20
1 2
3 4
100 9
```
Expected output
```
9
```