Thread Knots

There are n threads on the x-axis. The length of the i-th thread Ti is li and the location of its starting point is xi, both integers. We want to make one knot in each thread. The location of a knot must also be an integer. A knot can be made at any point on the thread, and the knot is assumed not to reduce the length of the thread. No thread is totally contained by another, meaning that there are no two threads Ti and Tj (i ≠ j) such that xj ≤ xi and xi+li ≤ xj+lj.

We want to choose the knot location for each thread so that the distance between the closest two knots is as large as possible.

For example, the figures below show the knot locations for six threads. A knot location is denoted by a point. All threads actually lie on the x-axis, but they are drawn separately to distinguish them. In Figure I.1, the distance between the closest two knots is 20. However, if we place the knot for T2 at a different location as shown in Figure I.2, the distance between the closest two knots becomes 25, which is the value this problem asks for.

Figure I.1: An example of knots for 6 threads.

Figure I.2: Another example with a different knot location for T2.

Given information about the n threads, write a program that computes the maximum distance between the closest two knots.

Your program reads from standard input. The input starts with a line containing one integer n (2 ≤ n ≤ 100,000), the number of threads. In the following n lines, the i-th line contains two integers xi (0 ≤ xi ≤ 109) and li (1 ≤ li ≤ 109), where xi and li are the location of the starting point and the length of the i-th thread. No thread is totally contained by another, meaning that there are no two threads Ti and Tj (i ≠ j) such that xj ≤ xi and xi+li ≤ xj+lj.

Your program writes to standard output. Print exactly one line. The line must contain an integer, the maximum distance between the closest two knots.