지원 요청의 하루 마감

문제

한 회사의 사내 IT 지원팀은 직원들이 보낸 지원 요청을 날짜별로 처리한다. 지원 요청 한 건은 한 번의 처리로 완료되며, 일부만 처리한 상태로 남겨 두는 일은 없다. 기록을 시작하기 전에는 처리하지 못한 요청이 한 건도 없다. 지원팀은 연속된 N일 동안의 접수량과 처리 가능량을 기록했다. 각 날짜에는 먼저 그날의 새 요청이 모두 접수된다. 전날 마감 후 남아 있던 요청이 있다면 새 요청과 함께 처리 대상이 된다. 지원팀은 그날 처리 대상인 요청 중에서 가능한 한 많은 요청을 처리한다. 다만 그날 정해진 처리 가능량보다 많은 요청을 처리할 수는 없다. 기존 요청과 새 요청 중 어느 것을 먼저 처리하는지는 요청 수를 계산하는 데 영향을 주지 않는다. 어떤 날의 처리 대상이 9건이고 처리 가능량이 6건이라면, 그날에는 6건을 처리하고 3건을 다음 날로 넘긴다. 처리 대상이 처리 가능량보다 적으면 모든 요청을 처리한다. 이때 사용하지 않은 처리 가능량은 사라지며, 다음 날의 처리 가능량에 더해지지 않는다. 새 요청이 없거나 처리 가능량이 0인 날도 같은 규칙을 따른다. 지원팀은 기록 기간의 업무량을 확인하기 위해 두 가지 값을 구하려고 한다. 첫 번째 값은 N일 동안 실제로 처리를 완료한 요청의 총수이다. 두 번째 값은 각 날짜의 처리가 모두 끝난 직후 남아 있는 요청 수 중 가장 큰 값이다. 하루 중 새 요청을 접수한 직후의 수는 두 번째 값을 구할 때 사용하지 않는다. 마감 후 남은 요청 수가 가장 큰 날이 여러 번 있어도 그 요청 수를 한 번만 출력한다. 모든 날에 요청을 남기지 않았다면 두 번째 값은 0이다. 마지막 날 이후의 추가 처리는 기록에 포함하지 않는다. 날짜별 기록을 받아 지원팀이 원하는 두 값을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N이 주어진다.
다음 N개의 줄에는 날짜 순서대로 두 정수 A_i, C_i가 공백으로 구분되어 주어진다. A_i는 i번째 날 새로 접수된 요청 수이고, C_i는 그날의 처리 가능량이다.
1 ≤ N ≤ 1,000이며, 모든 i에 대해 0 ≤ A_i, C_i ≤ 1,000이다.

출력

N일 동안 실제로 처리를 완료한 요청의 총수와 하루 마감 후 남은 요청 수의 최댓값을 순서대로 공백으로 구분하여 한 줄에 출력한다. 두 값은 모두 정수이다.

4
5 2
1 3
0 4
7 2

8 5

3
0 8
4 10
2 2

6 0

3
3 0
3 0
3 0

0 9

출처: Devin.KR 자체 제작