Convention II

공항 픽업이 오래 지연되었음에도 소들의 풀 먹기 대회는 지금까지 순조롭게 진행되고 있다. 이 대회에는 전 세계에서 소들이 모여들었다.

그러나 대회의 주요 행사가 Farmer John의 일정 관리에 또 다른 골칫거리가 될 것 같다. 그의 농장에 있는 아주 작은 목초지에는 세상에서 가장 맛있다고 소문난 희귀한 풀이 자란다. 그래서 대회에 참가한 $N$마리의 소($1 \leq N \leq 10^5$) 모두가 이 풀을 맛보고 싶어 한다. 목초지가 너무 좁아서 한 번에 한 마리의 소만 들어갈 수 있으므로 긴 줄이 생길 것이다.

Farmer John은 각 소 $i$가 특별한 목초지에 도착할 예정인 시각 $a\_i$와, 자기 차례가 되면 그 특별한 풀을 먹으며 보낼 시간 $t\_i$를 알고 있다. 소 $i$가 풀을 먹기 시작하면 $t\_i$만큼 시간을 다 보낸 뒤에 떠나고, 그동안 도착한 다른 소들은 기다려야 한다. 목초지가 다시 비었을 때 기다리고 있는 소가 여러 마리라면, 서열이 가장 높은 소가 다음으로 풀을 먹는다. 어떤 소가 다른 소가 먹기를 마치는 순간 도착한 경우에도 "기다리는" 것으로 본다. 마찬가지로, 아무 소도 먹고 있지 않을 때 여러 소가 정확히 같은 시각에 도착하면 서열이 가장 높은 소가 다음으로 먹는다.

FJ를 도와 어떤 소가 줄을 서서 기다려야 할 수 있는 최대 시간(시각 $a\_i$와 그 소가 먹기 시작하는 시각 사이)을 구하여라.

첫째 줄에 $N$이 주어진다. 다음 $N$개 줄은 $N$마리의 소에 대한 정보를 서열 순으로(가장 서열이 높은 소가 먼저) 나타낸다. 각 줄에는 한 마리의 소에 대한 $a\_i$와 $t\_i$가 주어진다. $t\_i$는 $10^4$ 이하인 양의 정수이고, $a\_i$는 $10^9$ 이하인 양의 정수이다.

모든 소를 통틀어 가능한 가장 긴 기다림 시간을 출력하여라.

이 예에는 5마리의 소가 있다(입력 순서에 따라 1..5로 번호를 붙인다). 소 4가 가장 먼저 도착하고(시각 10), 그 소가 먹기를 마치기(시각 27) 전에 소 1과 소 3이 도착한다. 소 1의 서열이 더 높으므로 소 1이 다음으로 먹게 되고, 도착 시각보다 2만큼 더 기다렸다. 소 1은 시각 30에 먹기를 마치고, 그다음 소 3이 먹기 시작하는데 시작 시각보다 10만큼 더 기다렸다. 아무 소도 먹지 않는 틈이 지난 뒤 소 5가 도착하고, 소 5가 먹는 동안 소 2가 도착하여 5만큼 늦게 먹는다. 도착 시각 대비 가장 오래 지연된 소는 소 3이다.