P9455 [Beginner Contest #14] Tower Overclocking (Hard Version).

There are $n$ towers on a straight road. They are numbered $1, 2, \cdots, n$ in order, and are located at distances $a _ 1, a _ 2, \cdots, a _ n$ from the start of the road ($a _ 1 < a _ 2 < \cdots < a _ n$). Each tower initially has a communication radius $b _ 1, b _ 2, \cdots, b _ n$. This means that tower $i$ can communicate with towers whose positions are within the range $[a _ i - b _ i, a _ i + b _ i]$. Note in particular: for two towers A and B, B can transmit a signal to A if and only if A's **position** is within B's communication range. Note that this is not the same as “their communication ranges overlap, so they can communicate”. Now you can overclock these towers. Specifically, you may choose a voltage $k$, and then **all** towers will have their voltage increased by $k$, so their communication radii will each increase by $k$. Here $k$ can only be a non-negative integer. You are required to overclock the towers so that a signal can be transmitted from tower $1$ to tower $n$, with no restriction on the path (that is, you only need the signal to reach tower $n$ from tower $1$ in some way). However, unreasonable overclocking will seriously wear out the towers, so you want to make the overclocking voltage as small as possible. Compute the minimum voltage needed for overclocking to achieve the goal above.

The input has $n + 1$ lines. The first line contains an integer $n$, representing the number of towers. The next $n$ lines each contain two integers $a _ i, b _ i$, representing the position and the initial communication radius of each tower.

Output one line with one integer, representing the minimum voltage needed for overclocking to achieve the goal.

### Constraints For $100\%$ of the testdata, it is guaranteed that $2 \leq n \leq 5 \times 10 ^ 5$, and $0 \leq a _ i, b _ i \leq 10 ^ 9$. Translated by ChatGPT 5