원의 섬 위의 정사각형

원의 섬은 완전히 평평한 섬이고, 그 모양은 중심이 모두 x축 위에 있는 원과 그 원의 내부를 전부 합친 것이다.

원의 섬의 왕은 즉위 50주년을 기념해 섬에 커다란 정사각형 광장을 만들려고 한다. 광장은 될 수 있는 한 커야 한다. 광장 전체가 섬 위에 있어야 하고, 섬의 어느 부분이든 광장으로 쓸 수 있다. 모양은 정사각형이어야 하며, 한 변은 x축과 평행해야 한다.

섬을 이루는 원의 중심과 반지름이 주어진다. 만들 수 있는 가장 큰 정사각형의 한 변 길이를 구하여라.

원은 중심의 x좌표가 커지는 순서로 주어진다. 모든 $i$ $(1 \le i \le N-1)$에 대해 $i$번째 원과 $i+1$번째 원은 겹친다. 어떤 원도 나머지 원에 완전히 덮이지 않는다.

그림 1. 첫 번째 예제의 섬과 가장 큰 정사각형 하나

입력은 여러 개의 데이터 세트로 이루어지고, 데이터 세트는 30개를 넘지 않는다. 각 데이터 세트의 형식은 다음과 같다.

N
X1 R1
:
XN RN

첫 줄에 섬을 이루는 원의 개수 $N$ $(1 \le N \le 50000)$이 주어진다. 이어지는 $N$개의 줄 중 $i$번째 줄에는 두 정수 $X_i$ $(-100000 \le X_i \le 100000)$와 $R_i$ $(1 \le R_i \le 100000)$가 주어진다. $i$번째 원의 중심은 $(X_i, 0)$이고 반지름은 $R_i$이다.

다음을 가정해도 된다.

• 모든 $i$ $(1 \le i \le N-1)$에 대해 $X_i < X_{i+1}$이다.
• 모든 $i$ $(1 \le i \le N-1)$에 대해 $i$번째 원과 $i+1$번째 원은 적어도 한 점을 공유한다. 즉 $X_{i+1} - X_i \le R_i + R_{i+1}$이다.
• 모든 원에는 다른 어떤 원의 내부에도 경계에도 속하지 않는 점이 적어도 하나 있다.

입력의 끝은 0 하나만 있는 줄로 표시된다.

각 데이터 세트마다 가장 큰 정사각형의 한 변 길이를 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다.