Minimize Maximum Displacement for Interval Coverage

You are given n closed intervals on the number line: \(D_1, D_2, \ldots, D_n\). Each interval \(D_i\) is described by two integers \(a_i\) and \(b_i\) with \(a_i < b_i\). It is guaranteed that the sum of the lengths of these intervals is at least \(10000\).

You can shift (translate) each interval \(D_i = [a_i, b_i]\) by a value \(c_i\) (which may be positive, negative, or zero) to obtain a new interval \([a_i+c_i, b_i+c_i]\). By shifting the intervals appropriately, you can always arrange for their union to cover the entire interval \([0, 10000]\), that is, every point in \([0, 10000]\) is contained in at least one shifted interval.

Your goal is to choose the shifts \(c_1, c_2, \ldots, c_n\) so that the maximum displacement among all intervals, i.e. \[ \min \max_{1\le i\le n} |c_i|, \] is as small as possible. Output this minimum possible value.

Note: In your solution, if you shift an interval \(D_i = [a_i, b_i]\) by \(c_i\) then its new position is \([a_i+c_i, b_i+c_i]\) and you must have \(|c_i| \le X\) for all \(i\), where \(X\) is minimized.

inputFormat

The first line contains a single integer \(n\) (the number of intervals). Each of the following \(n\) lines contains two integers \(a_i\) and \(b_i\) (with \(a_i < b_i\)), representing the endpoints of the interval \(D_i\). It is guaranteed that the sum of the lengths (i.e. \(\sum_{i=1}^n (b_i - a_i)\)) is at least \(10000\).

outputFormat

Output a single integer, which is the minimum possible value of \(X = \max_{1\le i\le n} |c_i|\) such that it is possible to shift every interval \(D_i\) by some \(c_i\) with \(|c_i| \le X\) so that the union of the shifted intervals covers \([0, 10000]\).

sample

2
0 5000
5000 10000

0