퇴근 전 지원 기록

문제

한 회사의 사내 IT 지원실은 직원들이 보낸 지원 요청을 처리한다. 지원실은 매일 업무가 끝날 때 아직 처리하지 못한 요청의 수를 기록한다. 담당자는 이 기록을 모두 더한 값을 이용하여 요청이 얼마나 오래 밀려 있었는지 살펴보려 한다. 관찰 기간은 연속된 N일이며, 첫날 업무를 시작하기 전에는 처리하지 못한 요청이 없다. i일에는 새로운 요청 A_i개가 들어오고, 지원실은 그날 요청을 최대 B_i개까지 처리할 수 있다. 모든 요청은 처리에 필요한 작업량이 같으며, 요청 하나를 처리하면 그 요청은 즉시 완료된다. 매일 새로운 요청이 먼저 모두 들어온 뒤 처리를 시작한다. 전날까지 남아 있던 요청과 그날 들어온 요청을 합친 수가 B_i 이상이면 정확히 B_i개를 처리한다. 합친 수가 B_i보다 작으면 남아 있는 요청을 모두 처리한다. 처리할 요청이 없으면 아무것도 처리하지 않는다. 사용하지 않은 처리 가능 수량은 다음 날로 넘기지 않는다. 그날 처리를 마친 뒤에도 남아 있는 요청은 다음 날로 넘어간다. 관찰 기간 중에는 요청이 취소되거나 지원실 밖에서 처리되는 일이 없다. 새로운 요청이 하나도 들어오지 않는 날이나 요청을 하나도 처리할 수 없는 날도 있을 수 있다. 지원실이 구하려는 값은 N일 동안 매일 업무가 끝난 직후 남아 있는 요청 수의 합이다. 같은 요청이 여러 날 동안 남아 있다면, 그 요청은 남아 있었던 날마다 합에 한 번씩 포함된다. 따라서 이 값은 관찰 기간에 들어온 요청의 총수나 마지막 날 남은 요청 수와 다를 수 있다. 모든 날의 업무 종료 시점에 남은 요청이 없다면 구하려는 값은 0이다. 매일의 새로운 요청 수와 처리 가능 수량을 보고 이 값을 구하는 프로그램을 작성한다.

입력

첫째 줄에 관찰 기간 N이 주어진다. N은 1 이상 1,000 이하의 정수다.
다음 N개 줄 중 i번째 줄에 i일의 새로운 요청 수 A_i와 처리 가능 수량 B_i가 공백으로 구분되어 주어진다. A_i와 B_i는 각각 0 이상 1,000 이하의 정수다. 날짜는 첫날부터 순서대로 주어진다.

출력

N일 동안 매일 업무가 끝난 직후 남아 있는 요청 수의 합을 정수 하나로 출력한다. 합이 0이면 0을 출력한다.

4
5 2
1 2
0 1
4 2

9

3
0 0
3 5
2 2

0

3
2 0
2 0
2 0

12

출처: Devin.KR 자체 제작