Description

There are $n$ closed intervals on the number line: $D_1, \cdots ,D_n$.

Interval $D_i$ is described by a pair of integers $[a_i,b_i]$, satisfying $a_i<b_i$.

It is known that the sum of the lengths of these intervals is at least $10000$.

Therefore, by shifting these intervals appropriately, you can always make their union cover $[0,10000]$. That is, every point in the interval $[0,10000]$ lies in at least one interval.

You want to find a shifting method that minimizes the maximum shift amount among all intervals.

Specifically, suppose you shift $D_i$ to $[a_i+c_i,b_i+c_i]$. You want to minimize $\max\limits_{i=1}^n\{|c_i|\}$.

Input Format

The first line contains an integer $n$, indicating the number of intervals.

The next $n$ lines each contain two integers $a_i,b_i$, separated by a space, representing the interval $[a_i,b_i]$.

It is guaranteed that the sum of the lengths of the intervals is at least $10000$.

Output Format

Output a number, representing the answer. If the answer is an integer, output only the integer part. If the answer is not an integer, round it to one decimal place.

2
10 5010
4980 9980

20

4
0 4000
3000 5000
5001 8000
7000 10000

0.5

Hint

Sample Explanation

Sample 1: Move the first interval $10$ units to the left; move the second interval $20$ units to the right.

Sample 2: Move the $2$-nd interval $0.5$ units to the right; move the $3$-rd interval $0.5$ units to the left.

Constraints

For $30\%$ of the test cases, $1 \le n \le 10$.

For $100\%$ of the test cases, $1 \le n \le 10000$, $0 \le a_i<b_i \le 10000$.

Translated by ChatGPT 5