지원 요청 마감 기록

문제

한 회사의 사내 IT 지원 창구는 직원들이 보낸 요청을 날짜별로 처리한다. 창구는 하루가 시작할 때 그날 새로 도착한 요청을 모두 접수하고, 접수가 끝난 뒤 그날의 처리 가능 건수만큼 요청을 처리한다. 요청 한 건을 처리하면 대기 중인 요청 수가 정확히 1 줄어든다. 요청마다 필요한 작업량은 같다고 가정한다. 기록을 시작하기 전에는 대기 중인 요청이 없다. 전날 처리하지 못한 요청은 사라지지 않고 다음 날로 넘어간다. 따라서 어떤 날 처리할 수 있는 대상은 전날부터 남아 있던 요청과 그날 새로 도착한 요청을 합친 것이다. 그 수가 그날의 처리 가능 건수보다 작으면 대기 중인 요청을 모두 처리하고 업무를 마친다. 남는 처리 능력을 다음 날에 더해 주지는 않는다. 지원 담당자는 N일 동안 실제로 처리한 요청의 총건수와 마지막 날 업무가 끝난 뒤 남은 요청 수를 확인하려 한다. 여기에 더해, 매일 업무가 끝난 직후의 대기 요청 수 중 가장 큰 값도 기록하려 한다. 새 요청을 접수한 직후나 처리 도중의 요청 수는 이 최댓값에 포함하지 않는다. 같은 최댓값이 여러 날 나타나도 값 하나만 구하며, 해당 날짜는 출력하지 않는다. 새 요청이 하나도 도착하지 않는 날이나 요청을 한 건도 처리할 수 없는 날이 있을 수 있다. 모든 날의 업무 종료 후 대기 요청 수가 0이면 기록할 최댓값도 0이다. 요청의 종류나 접수 순서는 세 결과에 영향을 주지 않으므로 따로 주어지지 않는다. 날짜 순서대로 주어진 기록을 이용해 세 값을 구한다. 마지막 날이 끝난 뒤 별도의 추가 처리 시간은 없으며, 그때 남아 있는 요청을 처리한 것으로 계산하지 않는다.

입력

첫째 줄에 기록할 날짜 수 N이 주어진다. 다음 N개 줄 중 i번째 줄에 i일의 새 요청 수 A_i와 처리 가능 건수 C_i가 공백으로 구분되어 주어진다. 모든 값은 정수이며, 1 ≤ N ≤ 1,000, 0 ≤ A_i, C_i ≤ 1,000이다.

출력

실제로 처리한 요청의 총건수, 마지막 날 업무 종료 후 남은 요청 수, 각 날짜의 업무 종료 후 대기 요청 수의 최댓값을 이 순서대로 공백으로 구분하여 한 줄에 출력한다.

4
5 2
1 3
0 5
7 2

8 5 5

3
0 4
2 9
0 0

2 0 0

3
4 0
4 0
0 3

3 5 8

출처: Devin.KR 자체 제작