지원 창구의 남은 요청

문제

한 회사의 사내 IT 지원 창구는 직원들이 보낸 장비 점검 요청을 처리한다. 담당자는 앞으로 N일 동안의 요청 수와 처리 가능 건수를 정리해 두었다. 첫째 날 업무를 시작하기 전에는 기다리는 요청이 하나도 없다. 각 요청은 한 건씩 세며, 요청 종류에 따른 차이는 없다. 요청 한 건을 처리하면 그 요청은 대기 목록에서 사라진다. 매일 업무는 두 단계로 진행된다. 먼저 그날 새로 들어온 요청을 모두 대기 목록에 추가한다. 그다음 담당자가 대기 중인 요청을 처리한다. i번째 날 새로 들어오는 요청은 A_i건이고, 그날 처리할 수 있는 최대 요청 수는 B_i건이다. 담당자는 대기 중인 요청이 있는 동안에는 처리 가능 건수를 남겨 두지 않는다. 따라서 대기 요청이 B_i건 이상이면 정확히 B_i건을 처리하고, 그보다 적으면 기다리는 요청을 모두 처리한다. 그날 처리하지 못한 요청은 다음 날로 그대로 넘어간다. 반대로 처리할 수 있는 여유가 남았더라도 그 여유를 다음 날에 더해서 사용할 수는 없다. 예를 들어 업무를 시작할 때 기다리는 요청이 2건이고 새 요청이 3건 들어온 날에는 총 5건을 대상으로 처리한다. 이날 최대 4건을 처리할 수 있다면 하루가 끝났을 때 1건이 남는다. 요청을 처리하는 순서는 남는 요청의 개수에 영향을 주지 않으므로 따로 고려하지 않는다. 새 요청이 없는 날이나 한 건도 처리할 수 없는 날도 있을 수 있으며, 이런 날에도 같은 규칙을 적용한다. N번째 날의 요청 추가와 처리를 모두 마친 직후 대기 목록에 남아 있는 요청의 개수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 업무 일수 N이 주어진다.
다음 N개의 줄 중 i번째 줄에 A_i와 B_i가 공백으로 구분되어 주어진다.
1 ≤ N ≤ 1,000이고, 0 ≤ A_i, B_i ≤ 1,000이다. 입력에 등장하는 모든 수는 정수이다.

출력

N번째 날 업무가 끝난 직후 남아 있는 요청의 개수를 정수 하나로 출력한다. 남은 요청이 없으면 0을 출력한다.

3
5 2
1 3
4 2

3

3
0 7
4 9
2 2

0

출처: Devin.KR 자체 제작