창고의 하루 마감 기록

문제

물류 창고에서 한 종류의 상자를 관리하고 있다. 창고에는 업무를 시작하기 전에 상자가 하나도 없다. 관리자는 앞으로 N일 동안 매일 들어오는 상자 수와 그날 출고를 요청받은 상자 수를 기록했다. 상자는 모두 같은 종류이므로 어떤 상자를 먼저 출고하는지는 결과에 영향을 주지 않는다. 창고의 저장 공간에는 제한이 없으며, 보관 중인 상자가 사라지거나 손상되는 일도 없다. 하루의 작업은 반드시 입고, 출고, 마감 순서로 진행한다. i일 아침에는 A_i개의 상자가 들어온다. 전날 마감 때 남아 있던 상자가 있다면 새로 들어온 상자와 합쳐서 사용할 수 있다. 입고가 끝난 뒤에는 그날의 요청 수량 B_i개만큼 출고하려고 한다. 보유한 상자가 요청 수량 이상이면 정확히 B_i개를 출고한다. 보유한 상자가 더 적으면 가지고 있는 상자를 전부 출고하고, 그날의 나머지 요청은 취소한다. 취소된 요청은 다음 날로 넘기지 않는다. 다음 날에는 그날 새로 주어진 요청만 처리한다. 출고 후 남은 상자는 그대로 보관하여 다음 날로 넘긴다. 하루에 상자가 들어오지 않을 수도 있고 출고 요청이 없을 수도 있다. 요청 수량이 0이면 상자가 하나도 없어도 요청을 모두 처리한 것으로 본다. 관리자는 전체 기간의 실제 출고 수량 합계와 마지막 날 마감 후 남은 상자 수를 알고 싶다. 또한 요청 수량보다 적게 출고한 날이 있다면 그중 가장 이른 날의 번호를 확인하려고 한다. 날짜는 첫날을 1일로 하여 순서대로 번호를 붙인다. 모든 날에 요청을 전부 처리했다면 해당 날짜 대신 0을 기록한다. 입고량을 단순히 모두 더하는 것만으로는 날짜별 출고 가능 여부를 알 수 없으므로, 정해진 작업 순서를 지키면서 하루씩 처리해야 한다. 주어진 기록에 따라 관리자가 필요한 세 값을 구하는 프로그램을 작성한다.

입력

첫째 줄에 날짜 수 N이 주어진다. N은 1 이상 90,000 이하의 정수다.
다음 N개 줄 중 i번째 줄에 i일의 입고 수량 A_i와 출고 요청 수량 B_i가 공백으로 구분되어 주어진다. A_i와 B_i는 각각 0 이상 9 이하의 정수다.

출력

실제 출고 수량의 합계, 마지막 날 마감 후 남은 상자 수, 요청보다 적게 출고한 가장 이른 날짜를 한 줄에 공백으로 구분하여 출력한다. 요청보다 적게 출고한 날이 없으면 세 번째 값으로 0을 출력한다.

5
4 1
0 5
7 2
1 3
0 4

12 0 2

3
0 0
9 2
0 3

5 4 0

1
0 6

0 0 1

출처: Devin.KR 자체 제작