실의 매듭

x축 위에 n개의 실이 있다. i번째 실 Ti의 길이는 li, 시작점의 위치는 xi이며 둘 다 정수이다. 각 실에 매듭을 하나씩 만들려고 한다. 매듭의 위치도 정수여야 한다. 매듭은 실 위의 임의의 점에 만들 수 있으며, 매듭을 만들어도 실의 길이는 줄어들지 않는다고 가정한다. 어떤 실도 다른 실에 완전히 포함되지 않는다. 즉, xj ≤ xi이고 xi+li ≤ xj+lj인 두 실 Ti와 Tj (i ≠ j)는 존재하지 않는다.

가장 가까운 두 매듭 사이의 거리를 최대한 크게 만들기 위해 각 실의 매듭 위치를 정하려고 한다.

예를 들어, 아래 그림은 여섯 개의 실에 매듭을 만든 위치를 나타낸다. 매듭의 위치는 점으로 표시한다. 모든 실은 실제로 x축 위에 놓여 있지만, 서로 구별하기 위해 따로 그렸다. 그림 I.1에서 가장 가까운 두 매듭 사이의 거리는 20이다. 그러나 그림 I.2처럼 T2의 매듭을 다른 위치에 만들면 가장 가까운 두 매듭 사이의 거리가 25가 되며, 이것이 이 문제에서 구하려는 값이다.

그림 I.1: 여섯 개의 실에 매듭을 만든 예.

그림 I.2: T2의 매듭 위치를 다르게 한 또 다른 예.

n개의 실에 대한 정보가 주어질 때, 가장 가까운 두 매듭 사이의 거리의 최댓값을 계산하는 프로그램을 작성하라.

프로그램은 표준 입력에서 데이터를 읽는다. 입력의 첫째 줄에는 실의 개수 n (2 ≤ n ≤ 100,000)이 주어진다. 다음 n개 줄 중 i번째 줄에는 두 정수 xi (0 ≤ xi ≤ 109)와 li (1 ≤ li ≤ 109)가 주어지며, xi와 li는 각각 i번째 실의 시작점 위치와 길이를 나타낸다. 어떤 실도 다른 실에 완전히 포함되지 않는다. 즉, xj ≤ xi이고 xi+li ≤ xj+lj인 두 실 Ti와 Tj (i ≠ j)는 존재하지 않는다.

프로그램은 표준 출력에 결과를 쓴다. 정확히 한 줄을 출력한다. 그 줄에는 가장 가까운 두 매듭 사이의 거리의 최댓값을 나타내는 정수가 들어가야 한다.