Minimum Rope Length for Descending Pipes

You are on the highest steel pipe in a building with \(n\) steel pipes. The i-th steel pipe has height \(h_i\) and value \(v_i\). You have a pair of scissors and a rope. Your goal is to descend from the starting pipe down to the ground (height 0) following a sequence of jumps. However, the sequence of the values of the pipes you land on must be non-decreasing (i.e. each value is no smaller than the previous one).

Note that some pipes may have the same height, meaning that at the same height you can choose a pipe with a different value as your landing spot.

Your rope’s initial length must be a positive integer. Using a technique (the "loop-hanging method") during descent, you can later recover a rope with a non‐integer length. In effect, the required rope length is determined by the maximum vertical gap you need to overcome in a single jump.

For any jump between two pipes, or between a pipe and the ground, if you are at a pipe with height \(h_i\) and jump to a pipe with height \(h_j\) (or to the ground, which is at height 0), the rope must be long enough so that \(h_i - h_j \leq L\). Additionally, when jumping between pipes, the destination pipe must have a value not less than the current pipe (i.e. \(v_j \ge v_i\)).

Determine the minimum required initial rope length \(L\) (a positive integer) that allows you to descend to the ground following these rules.

inputFormat

The first line contains a positive integer \(n\) representing the number of steel pipes. Each of the following \(n\) lines contains two integers \(h_i\) and \(v_i\) separated by a space, representing the height and the value of the \(i\)-th steel pipe.

outputFormat

Output a single integer: the minimum required rope length \(L\) that allows you to descend to the ground following the conditions.

sample

3
10 2
7 2
3 3

4