내일 할거야

아, 과제 하기 싫다. 아무것도 하기 싫다. 더 적극적이고 격렬하게 아무것도 하기 싫다.

책상 위에 $n$개의 과제 목록이 적혀 있다. 각 과제 $i$는 끝내는 데 $d_i$일이 걸리고, 오늘로부터 $t_i$일 안에 제출해야 한다. 즉, 오늘을 0일이라고 하면 $t_i$일이 끝나기 전까지 과제 $i$를 완료해야 한다. 한 과제는 한번 시작하면 중간에 쉬지 않고 연속해서 끝까지 해야 하며, 한 번에 하나의 과제만 할 수 있다.

오늘(0일)은 아무것도 하지 않기로 했다. 나아가 내일부터도 가능한 한 오래 아무것도 하지 않고 놀고 싶다.

모든 과제를 마감 안에 끝낼 수 있다고 할 때, 내일(1일)부터 연속으로 최대 며칠 동안 아무것도 하지 않고 놀 수 있는지 구하라.

첫째 줄에 과제의 개수를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어진다.

이후 $n$개의 줄에 각 과제를 나타내는 두 정수 $d_i$, $t_i$ ($1 \le d_i, t_i \le 10^9$)가 공백으로 구분되어 주어진다. 오늘은 0일이다.

오늘 아무것도 하지 않아도 모든 과제를 마감 안에 끝낼 수 있는 방법이 항상 존재함이 보장된다.

내일(1일)부터 연속으로 최대 며칠 동안 놀 수 있는지를 한 줄에 출력한다. 예를 들어 답이 0이면 내일부터 과제를 시작해야 하고, 답이 1이면 모레부터 과제를 시작해야 한다.

첫 번째 예제의 경우, 1–5일에는 놀고, 6–7일에는 첫 번째 과제를, 8–10일에는 세 번째 과제를 한다. 11–12일에는 놀고, 13일에 두 번째 과제를 한다.