버스 배정

면접 대비

시간 제한2초메모리 제한2048 MB

요약

정류장마다 내리는 사람 수와 타는 사람 수가 주어질 때, 버스에 동시에 있는 승객 수의 최댓값을 구합니다.

난이도: 쉬움10점 중 2점
유형: 시뮬레이션, 배열
정답자: 아직 제출이 없습니다

문제

Institution for Carrying People Carefully는 Line Town의 유명한 Line Bus를 관리한다. Line Bus는 1번부터 $n$ 번까지 번호가 붙은 $n$ 개의 정류장을 지난다. $i$ 번 정류장에서는 먼저 $a_i$ 명이 내리고, 그다음 $b_i$ 명이 탄다. 버스는 1번 정류장에서 빈 상태로 출발하여 번호 순서대로 정류장을 지나고, $n$ 번 정류장에 도착하면 비워진다.

Line Bus에 탄 사람은 반드시 좌석에 앉아야 한다. 용량이 $c$ 인 버스에는 승객용 좌석이 정확히 $c$ 개 있고, 승객 한 명이 좌석 하나를 차지한다. 운전기사는 좌석 수에 포함하지 않는다. 이 기관은 Line Bus를 운행하는 데 필요한 버스의 최소 용량을 알고 싶어 한다.

입력

첫 번째 줄에 정수 $n$ 이 주어진다 ( $2 \le n \le 2 \cdot 10^5$ ).

이어지는 $n$ 개의 줄에는 정수 $a_i$ 와 $b_i$ 가 한 줄에 하나씩 주어진다 ( $0 \le a_i, b_i \le 10^9$ ). 적어도 한 명은 버스에 타며, 모든 정류장에서 탑승한 사람의 총합은 $10^9$ 이하이고, 버스는 $n$ 번 정류장을 지난 후 비어 있다.

출력

버스의 최소 용량을 나타내는 정수 하나를 출력한다.

예제1

예제 1
입력
```
4
0 3
1 2
2 1
3 0
```
예상 출력
```
4
```