Optimal Banquet Meeting Time

In the glorious ancient city of Chang'an during the Tang Dynasty, officials lived in various districts arranged along the main avenue known as the Zhuque Street (which we treat as a number line). Each official resides at an integer coordinate x_i on this line. Every month they hold a banquet at a meeting point x₀ (which can be any point on the line, not necessarily an integer).

For the i-th official, the time required to reach the banquet is given by:

[ |x_i - x_0| + t_i ]

where ti is the time the official spends preparing and |xi - x0| is the travel time. Note that the banquet cannot start until every official has arrived. Hence, if the banquet is held at x₀, the start time of the banquet is

[ T(x_0) = \max_{1 \le i \le n} { |x_i - x_0| + t_i } ]

The officials wish to begin the banquet as early as possible. Your task is to help them choose the optimal banquet location x₀ (which may be any real number) so that the banquet start time T(x₀) is minimized. Output the minimum possible start time.

Note: The absolute value \(|x_i - x_0|\) denotes the nonnegative difference between x_i and x₀.

inputFormat

The first line contains a positive integer n, the number of officials.

Each of the following n lines contains two space-separated non-negative integers: xi (the position of the official) and ti (the time needed for preparation).

It is guaranteed that xi is an integer.

outputFormat

Output a single real number representing the minimum possible banquet start time. The answer will be accepted if it has an absolute or relative error of no more than 10^-6.

sample

1
5 3

3.000000