다운로드

택희는 한 곡을 여러 조각으로 나누어 순서대로 다운로드하려고 한다. 각 조각마다 재생 시간과 다운로드에 걸리는 시간이 정해져 있다.

택희는 모든 조각의 다운로드가 끝나기 전에 노래를 재생하기 시작할 수 있다. 하지만 한 번 재생을 시작하면 노래는 마지막까지 끊김 없이 재생되어야 한다. 어떤 조각을 재생하려면 그 조각 전체의 다운로드가 이미 끝나 있어야 한다.

다운로드를 시작한 뒤 몇 초가 지난 시점에 재생을 시작해야 끝까지 끊김 없이 들을 수 있는지 구하라. 가능한 시점이 여러 개라면 가장 이른 시점을 출력한다.

첫째 줄에 조각의 수 N이 주어진다. (1 <= N <= 100,000)

다음 N개의 줄에는 각 조각의 재생 시간 D와 다운로드에 걸리는 시간 V가 주어진다. (1 <= D, V <= 1000)

조각은 다운로드하고 재생해야 하는 순서대로 주어진다.

다운로드를 시작한 뒤 몇 초 후에 재생을 시작하면 끊김 없이 끝까지 들을 수 있는지 출력한다.