오늘 남은 포장 주문

문제

한 온라인 쇼핑몰은 매일 정해진 시간에 주문 상품을 포장한다. 주문 하나를 처리하려면 포장 작업 한 번이 필요하며, 모든 주문의 작업량은 같다. 쇼핑몰은 앞으로 N일 동안의 새 주문 수와 날짜별 포장 한도를 기록해 두었다. 담당자는 이 기록에 따라 작업했을 때 마지막 날에 몇 개의 주문이 남는지 확인하려 한다. 첫째 날이 시작되기 전에는 포장을 기다리는 주문이 없다. 매일 그날의 새 주문이 먼저 모두 접수되고, 그 뒤에 포장 작업을 진행한다. 전날까지 남아 있던 주문과 그날 새로 접수된 주문은 모두 그날 포장할 수 있다. 다만 하루에 포장할 수 있는 주문 수는 그날의 포장 한도를 넘을 수 없다. 작업자는 포장을 기다리는 주문이 있는 동안 한도에 도달할 때까지 계속 포장한다. 기다리는 주문 수가 한도보다 적거나 같으면 그 주문을 모두 포장하고 하루 작업을 끝낸다. 기다리는 주문 수가 한도보다 많으면 한도만큼 포장하고 나머지 주문을 다음 날로 넘긴다. 포장한 주문은 이후의 대기 주문 수에 포함하지 않는다. 어떤 날에 포장 한도를 모두 사용하지 못하더라도 남은 한도를 다음 날로 넘기지는 않는다. 예를 들어 기다리는 주문이 2개이고 그날의 한도가 5개라면 2개만 포장한다. 이때 사용하지 않은 한도 3개가 다음 날의 한도에 더해지는 일은 없다. 새 주문이 없는 날에도 이전에 남은 주문은 포장할 수 있으며, 포장 한도가 0인 날에는 주문을 하나도 포장하지 못한다. 주문 취소나 추가 작업은 발생하지 않는다. 날짜별 기록을 첫째 날부터 순서대로 적용하여 N번째 날의 포장 작업까지 모두 마친 직후에 남아 있는 주문 수를 구하는 프로그램을 작성한다. 모든 주문을 처리했다면 남은 주문 수는 0이다.

입력

첫째 줄에 날짜 수 N이 주어진다. 다음 N개 줄 중 i번째 줄에 i번째 날의 새 주문 수 A_i와 포장 한도 C_i가 공백으로 구분되어 주어진다. 모든 입력값은 정수이며, 1 ≤ N ≤ 1,000, 0 ≤ A_i ≤ 1,000, 0 ≤ C_i ≤ 1,000이다.

출력

N번째 날의 포장 작업을 마친 직후에 남아 있는 주문 수를 정수 하나로 출력한다. 남은 주문이 없으면 0을 출력한다.

4
7 3
1 4
0 2
5 1

4

3
0 10
6 2
1 1

4

1
8 10

0

출처: Devin.KR 자체 제작