버스의 가장 붐빈 출발

문제

마을을 지나는 한 버스 노선에서는 승객 수에 맞춰 안내 인력을 배치하려 한다. 담당자는 버스가 정류장을 떠날 때마다 안에 타고 있는 승객 수를 확인하고, 그중 가장 큰 값을 기록하기로 했다. 버스의 좌석 수나 서 있는 승객의 수는 따로 구분하지 않으며, 버스 안에 있는 모든 승객을 한 명씩 센다. 운전자는 승객 수에 포함하지 않는다. 이번에 살펴볼 운행 기록에는 방문 순서대로 N개의 정류장이 들어 있다. 버스는 첫 번째 정류장에 도착하기 직전에는 승객이 한 명도 없는 상태다. 각 정류장에서는 먼저 일부 승객이 내리고, 그다음 새로운 승객이 탄다. 정류장에서 내리는 사람 수와 타는 사람 수는 각각 정수로 기록되어 있다. 아무도 내리지 않거나 아무도 타지 않는 정류장도 있을 수 있다. 정류장과 정류장 사이에서는 승객이 타거나 내리지 않는다. 따라서 어떤 정류장을 떠난 직후의 승객 수는 다음 정류장에 도착할 때까지 그대로 유지된다. 각 정류장에서 내리는 사람 수는 그 정류장에 도착했을 때 버스 안에 있던 승객 수를 넘지 않는다. 또한 승객이 모두 타고 난 뒤 버스 안의 승객 수는 항상 1,000 이하가 되도록 기록이 주어진다. 담당자가 비교하는 값은 각 정류장에서 내릴 사람과 탈 사람의 이동이 모두 끝난 직후의 승객 수다. 승객이 내리기만 한 중간 순간의 수를 따로 기록하지 않는다. N번째 정류장 이후에도 버스는 운행을 이어 가므로, 마지막 기록에서 모든 승객이 내려야 하는 것은 아니다. 마지막 정류장을 떠날 때의 승객 수도 비교 대상에 포함한다. 방문한 정류장들의 기록이 주어졌을 때, 정류장을 떠난 직후의 승객 수 중 최댓값을 구하는 프로그램을 작성한다. 같은 최댓값이 여러 번 나타나더라도 그 값만 한 번 출력한다. 모든 기록에서 타는 사람이 없어 승객 수가 계속 0이었다면 0을 출력한다.

입력

첫째 줄에 정류장 수를 나타내는 정수 N이 주어진다.
다음 N개 줄의 i번째 줄에 i번째 정류장에서 내리는 사람 수 D_i와 타는 사람 수 U_i가 공백으로 구분되어 주어진다.
1 ≤ N ≤ 1,000
0 ≤ D_i, U_i ≤ 1,000
첫 번째 정류장 도착 직전의 승객 수는 0이다.
각 D_i는 해당 정류장 도착 시의 승객 수 이하이며, 각 정류장에서 승하차를 마친 직후의 승객 수는 0 이상 1,000 이하임이 보장된다.

출력

각 정류장을 떠난 직후의 승객 수 중 최댓값을 정수 하나로 출력한다.

4
0 7
2 3
5 1
1 0

8

3
0 0
0 0
0 0

0

출처: Devin.KR 자체 제작