# 4392 : Thread Knots

- 제한시간
- 1000 ms

- 메모리제한
- 512 MB

- 해결횟수
- 2 회

- 시도횟수
- 3 회

### 문제

There are n threads on the x-axis. The length of the i-th thread, say T_{i}, is denoted by l_{i} and the location of its starting point by x_{i}, both being integers. We want to make a knot in each thread. The location of the knot must also be an integer. The knot can be made at any point in the thread and it is assumed that the length of the thread is not reduced by the knot. You can assume that no thread is totally contained by another, which means that there are no two thread T_{i} and T_{j} (i ≠ j) such that x_{j} ≤ x_{i} and x_{i}+l_{i} ≤ x_{j}+l_{j}.

We want to determine the location of the knot for each thread in order to make the distance between the closest two neighboring knots as big as possible.

For example, the figures below show the locations of the knots for six threads. The location of a knot is denoted by a point. All the threads actually lie on the x-axis, however, they are drawn separately to distinguish each other. In Figure I.1, the distance between the closest two knots is 20. However, if we make the knot for T_{2} at different location as shown in Figure I.2, the distance between the closest two knots becomes 25, which is what this problem requests.

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

### 입력형식

Your program is to read from standard input. The input starts with a line containing one integer, n (2 ≤ n ≤ 100,000), where n is the number of threads. In the following n lines, the i-th line contains two integers x_{i} (0 ≤ x_{i} ≤ 10^{9}) and l_{i} (1 ≤ l_{i} ≤ 10^{9}), where x_{i} and l_{i} denote the location of the starting point and the length of the i-th thread, respectively, You can assume that no thread is totally contained by another, which means that there are no two threads T_{i} and T_{j} (i ≠ j) such that x_{j} ≤ x_{i} and x_{i}+l_{i} ≤ x_{j}+l_{j}.

### 출력형식

Your program is to write to standard output. Print exactly one line. The line should contain an integer which is the maximum distance between two closest knots.

## 입력 예6 0 67 127 36 110 23 50 51 100 12 158 17 |
## 출력 예25 |

## 입력 예6 0 40 10 55 45 28 90 40 83 30 120 30 |
## 출력 예30 |

## 입력 예3 0 20 40 10 100 20 |
## 출력 예50 |