식사 대기 시간

셰프 병철은 국가대표 선수들을 위해 특별한 음식을 대접하기로 한다. 셰프 병철의 레스토랑에는 특별한 음식이 있는데, 이것은 세계에서 가장 맛있는 음식이라고 한다. 식사에 참석한 모든 $N$ ($1 \leq N \leq 10^5$)명의 선수들은 모두 이 음식을 시식하고 싶어한다. 하지만 레스토랑이 매우 작아 한 번에 한 명만 수용할 수 있기 때문에 긴 대기 줄이 형성될 것으로 보입니다.

병철은 각 선수 $i$가 레스토랑에 도착하는 데 걸리는 시간 $a_i$와 자신의 차례가 되면 특별한 음식을 시식하는 데 소요되는 시간 $t_i$를 알고 있다. 선수 $i$가 음식을 먹기 시작하면, 그녀는 퇴장하기 전에 $t_i$의 전체 시간을 보낸다, 그 동안 다른 도착하는 선수들은 기다려야 한다. 

만약 레스토랑이 다시 시식 가능해지는 시점에 여러 선수들이 기다리고 있다면, 가장 연장자인 선수가 다음으로 음식을 시식하게 된다. 이를 위해, 한 선수가 끝나는 순간에 바로 도착한 선수는 "대기 중"으로 간주된다. 비슷하게, 한 선수가 현재 먹고 있지 않은 동안에 정확히 같은 시간에 도착하는 여러 선수들 중에서, 가장 연장자인 선수가 다음에 먹게 된다.

선수들 중에서 어느 선수가 가장 오랜 시간을 대기하게 되는지를 계산해주십시오(시간 $a_i$와 선수가 먹기 시작하는 시간 사이).

입력의 첫 줄에는 $N$이 있습니다. 다음 $N$ 줄에는 순차적으로 연장자 순서로 $N$ 선수의 세부 정보가 지정되어 있습니다(가장 나이 많은 선수가 처음). 각 줄에는 한 선수에 대한 $a_i$와 $t_i$가 있습니다. $t_i$는 양의 정수이며 각각 최대 $10^4$이고, $a_i$는 각각 최대 $10^9$의 양의 정수입니다.

모든 선수들에 대해 가장 긴 잠재적 대기 시간을 출력하십시오.