메신저의 하루 끝 숫자

문제

사내 메신저의 사용 현황을 확인하기 위해 한 대화방의 읽지 않은 메시지 수를 매일 기록한다. 기록을 시작하기 직전에는 읽지 않은 메시지가 하나도 없다. 각 날짜에는 새로 도착한 메시지 수와 사용자가 읽을 수 있는 최대 메시지 수가 주어진다. 날짜별 기록은 첫날부터 마지막 날까지 시간순으로 제공된다. 하루의 처리는 두 단계로 이루어진다. 먼저 그날 도착한 메시지를 모두 읽지 않은 메시지에 추가한다. 그다음 사용자가 메시지를 읽는다. 사용자는 현재 읽지 않은 메시지가 충분히 있다면 그날 읽을 수 있는 최대 개수만큼 읽고, 그보다 적게 있다면 남아 있는 메시지를 모두 읽는다. 읽은 메시지는 읽지 않은 메시지 수에서 빠진다. 메시지를 읽을 수 있는 개수가 남더라도 다음 날 미리 사용할 수는 없다. 두 단계를 모두 마친 뒤의 읽지 않은 메시지 수를 그날의 기록값으로 정한다. 읽지 않은 메시지는 삭제되지 않으므로 다음 날로 그대로 넘어간다. 같은 메시지를 여러 날 동안 읽지 않았다면 그 메시지는 여러 날짜의 기록값에 포함될 수 있다. 이 문제에서 구하려는 값은 서로 다른 메시지의 개수가 아니라 모든 날짜의 기록값을 더한 합이다. 예를 들어 어떤 날의 기록값이 0이라면 그날은 합에 0을 더한다. 새 메시지가 없는 날에도 이전 날짜에서 넘어온 메시지를 읽을 수 있으며, 읽을 수 있는 최대 개수가 0인 날에는 메시지를 하나도 읽지 않는다. 전체 기간에 메시지가 한 번도 도착하지 않으면 합은 0이다. 주어진 날짜들을 순서대로 처리하여 하루가 끝날 때마다 남은 읽지 않은 메시지 수의 합을 계산한다.

입력

첫째 줄에 기록할 날짜 수 N이 주어진다. N은 1 이상 1,000 이하의 정수이다. 다음 N개의 줄에는 날짜 순서대로 정수 A와 B가 공백으로 구분되어 주어진다. A는 그날 도착한 메시지 수이고 B는 그날 읽을 수 있는 최대 메시지 수이다. 0 ≤ A ≤ 1,000, 0 ≤ B ≤ 1,000이다.

출력

각 날짜의 하루 처리를 마친 뒤 남은 읽지 않은 메시지 수를 모두 더한 정수 하나를 출력한다.

4
5 2
1 3
0 4
6 1

9

3
0 5
0 0
0 1

0

3
2 0
2 0
2 0

12

출처: Devin.KR 자체 제작