ICPC 2019 Asia Regional – Seoul Problem- Thread Knots > 문제은행 : 정보올림피아드&알고리즘




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 Ti, is denoted by li and the location of its starting point by xi, 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 Ti and Tj (i ≠ j) such that xj ≤ xi and xi+li ≤ xj+lj.

 

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 T2 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 xi (0 ≤ xi ≤ 109) and li (1 ≤ li ≤ 109), where xi and li 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 Ti and Tj (i ≠ j) such that xj ≤ xi and xi+li ≤ xj+lj.

 


출력형식

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


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP