버터 녹이기

성현이는 바나나 푸딩을 만들기 위해 먼저 버터를 녹이려고 한다. 이를 위해 양쪽으로 무한히 뻗은 직선 모양의 프라이팬에 홀수 높이의 버터 $N$개를 올려놓고, 열을 가해서 녹인다. 위치가 $x$인 곳에 올려진 버터는 처음에 구간 $[x, x]$를 차지한다. 열을 가하면 처음 버터가 올려진 부분의 높이가 1이 될 때까지 1초마다 좌우로 1씩 퍼진다. 즉, $[L, R]$을 차지하던 버터는 1초 후 $[L-1, R+1]$을 차지한다. 다음 표는 위치 $x=5$, 높이 $h=7$인 버터가 녹는 과정이다.

녹는 도중에 서로 다른 두 버터가 섞일 수 있다. 두 버터가 섞인다는 것은, 각각 $[l_1, r_1]$과 $[l_2, r_2]$를 차지할 때 두 구간이 겹치는 것을 뜻한다. 즉, $[l_1, r_1] \cap [l_2, r_2] \neq \emptyset$인 경우이다. 다음 그림은 입력 예시 1의 상황이다.

2초가 지난 상황에서는 두 버터가 섞이지 않는다.

3초까지 가열하면 $x=2$에서 두 버터가 섞인다.

성현이는 어떤 두 버터도 섞이지 않을 때까지만 버터를 녹이고 싶다. 그러나 정수 시간만큼만 가열할 수 있다. 즉, 3초나 4초를 가열할 수는 있지만, 3.5초나 3.105초를 가열할 수는 없다. 각 버터의 처음 위치 $x$와 높이 $h$가 $N$개 주어졌을 때, 성현이가 가열할 수 있는 가장 긴 시간을 구하라.

첫째 줄에 성현이가 올린 버터의 수 $N$이 주어진다.

이어 $N$개의 줄에 걸쳐 버터가 놓인 좌표 $x_i$와 버터의 높이 $h_i$가 공백으로 구분되어 주어진다.

$N$

$x_1$ $h_1$

$x_2$ $h_2$

$\cdots$

$x_{N-1}$ $h_{N-1}$

$x_N$ $h_N$

성현이가 가열할 수 있는 가장 긴 시간을 출력한다. 성현이가 $10^{100}$초 이상 가열할 수 있다면 forever를 출력한다.

• $2 \leq N \leq 300\,000$
• $-10^9 \leq x_i \leq 10^9$
• $x_i$는 모두 다르다.
• $1 \leq h_i \leq 10^9-1$
• $h_i$는 홀수이다.
• $x_i$와 $h_i$는 모두 정수이다.