존(Farmer John) 아저씨가 개최한 '풀 뜯기 관심 소들을 위한 컨퍼런스'는 공항 픽업 과정에서 긴 지연이 있었음에도 불구하고 지금까지 아주 성공적으로 진행되고 있습니다.

이번 행사에는 전 세계에서 수많은 소들이 모여들었습니다.

하지만 컨퍼런스의 메인 이벤트가 존 아저씨에게 또 다른 일정 관리 지연 지옥을 선사할 것 같습니다.

아저씨의 농장에는 미식가 소들 사이에서 세계에서 가장 맛있다고 소문난 희귀한 풀이 자라는 아주 작은 목초지가 하나 있습니다.

그 결과, 컨퍼런스에 참석한 N마리의 모든 소가 이 풀을 맛보고 싶어 합니다.

그러나 이 목초지는 너무 좁아서 한 번에 단 한 마리의 소만 들어갈 수 있기 때문에, 필연적으로 아주 긴 대기 줄이 생길 수밖에 없습니다.

존 아저씨는 각 소 i가 특별 목초지에 도착할 예정 시간 ai와, 자기 차례가 왔을 때 풀을 맛보는 데 걸리는 시간 ti를 모두 알고 있습니다.

소 i가 풀을 먹기 시작하면 정해진 시간 ti를 온전히 다 채운 뒤에 떠나며, 이 시간 동안 새로 도착한 다른 소들은 줄을 서서 기다려야 합니다.

만약 목초지가 다시 비었을 때 여러 마리의 소가 기다리고 있다면, 나이(선임도, Seniority)가 가장 많은 소가 다음 차례로 목초지에 들어가게 됩니다.

어떤 소가 풀을 다 먹고 나오는 바로 그 타이밍에 딱 맞춰 도착한 소 역시 '기다리는 중'인 것으로 간주합니다.

이와 유사하게, 목초지가 비어 있는 상태에서 여러 마리의 소가 정확히 같은 시간에 동시에 도착한다면, 그중 나이가 가장 많은 소가 먼저 먹기 시작합니다.

입력으로 주어지는 소들의 순서는 나이가 많은 순서대로(가장 첫 줄에 주어지는 소가 가장 나이가 많음) 주어집니다.

모든 소들 중에서, 대기 줄에서 가장 오래 기다려야 하는 소의 최대 대기 시간(도착 시간 ai부터 풀을 먹기 시작하는 시간 사이의 간격)을 구하는 프로그램을 작성하세요.

입력

첫째 줄에 소의 수 N이 주어집니다. (1 <= N <= 100,000)

이어서 N개의 줄에 걸쳐, 나이가 많은 순서대로 각 소의 상세 정보가 주어집니다. 각 줄에는 해당 소의 도착 시간 ai와 먹는 시간 ti가 공백으로 구분되어 주어집니다.

ti는 10,000 이하의 양의 정수이며, ai는 10^9 이하의 양의 정수입니다.

출력

모든 소들의 대기 시간 중 가장 긴 대기 시간을 한 줄에 출력합니다.

예제 입력 1

5
25 3
105 30
20 50
10 17
100 10

예제 출력 1

10

힌트

이 예제에는 입력 순서(나이가 많은 순서)에 따라 1번부터 5번까지 번호가 매겨진 5마리의 소가 있습니다.

4번 소가 가장 먼저 도착(시간 10)하여 먹기 시작합니다.

4번 소가 다 먹기 전(시간 27)에 1번 소와 3번 소가 차례로 도착합니다.

목초지가 비는 시간 27에 두 소가 대기 중인데, 1번 소가 3번 소보다 나이가 많으므로(입력에서 더 먼저 주어졌으므로) 1번 소가 먼저 먹기 시작합니다. 이때 1번 소는 도착 시간(25)보다 2만큼 더 기다렸습니다.

1번 소는 시간 30에 끝나고, 이어서 기다리던 3번 소가 먹기 시작합니다. 3번 소는 도착 시간(20)보다 10만큼 더 기다렸습니다.

이후 한동안 아무도 먹지 않다가 시간 100에 5번 소가 도착해 먹기 시작합니다. 5번 소가 먹는 도중(시간 105)에 2번 소가 도착하여 대기하다가, 5번 소가 끝난 후 5만큼 기다린 끝에 먹기 시작합니다.

결과적으로 자신의 도착 시간에 비해 가장 오래 지연된 소는 3번 소(대기 시간 10)입니다.

출처

USACO 2018 December Contest, Silver