마감 후 가장 많은 상자

문제

한 물류 창고는 N일 동안 들어온 상자를 차례로 출고한다. 운영자는 매일 작업을 마친 뒤 창고에 남아 있는 상자 수를 기록한다. 이 기록을 이용하여 마감 후 남은 상자가 가장 많았던 날과 그 상자 수를 알아보려고 한다. 첫날 아침에 창고는 비어 있다. 하루의 작업은 입고와 출고의 순서로 진행된다. i일 아침에는 A_i개의 상자가 들어온다. 이 상자들은 전날 마감 후 남아 있던 상자에 더해진다. 그날의 출고 작업에서는 최대 C_i개의 상자를 내보낼 수 있다. 창고에 있는 상자 수가 C_i개 이상이면 정확히 C_i개를 출고하고, C_i개보다 적으면 있는 상자를 모두 출고한다. 출고가 끝난 뒤 남은 상자는 다음 날로 넘어간다. 상자가 부족하여 사용하지 못한 출고 능력은 다음 날로 넘어가지 않는다. 예를 들어 어느 날 출고 능력이 8개인데 상자가 3개뿐이면 3개를 출고하고 그날을 마친다. 사용하지 못한 5개만큼 다음 날에 더 출고할 수 있는 것은 아니다. 입고 수나 출고 능력이 0인 날도 있을 수 있다. 비교에 사용하는 값은 반드시 각 날의 출고가 끝난 뒤 남은 상자 수다. 아침 입고 직후에 상자가 잠시 많이 쌓였더라도 그 수를 기록에 포함하지 않는다. 또한 첫날이 시작되기 전의 빈 창고는 날짜가 있는 기록으로 취급하지 않는다. N일 중 마감 후 남은 상자 수의 최댓값을 M이라고 한다. M이 양수이고 그 값이 여러 날에 나타났다면 가장 이른 날의 번호를 D로 정한다. 날짜 번호는 1부터 시작한다. 모든 날에 상자가 남지 않아 M이 0이면 D도 0으로 정한다. 마지막 날 이후의 추가 출고는 고려하지 않는다. 주어진 입고 수와 출고 능력을 이용하여 D와 M을 구하는 프로그램을 작성한다.

입력

첫째 줄에 작업 일수 N이 주어진다.
다음 N개 줄 중 i번째 줄에 i일의 입고 수 A_i와 출고 능력 C_i가 공백으로 구분되어 주어진다.
모든 입력값은 정수다.
1 ≤ N ≤ 1,000
0 ≤ A_i ≤ 1,000
0 ≤ C_i ≤ 1,000

출력

첫째 줄에 날짜 D와 마감 후 남은 상자 수의 최댓값 M을 공백으로 구분하여 출력한다. 최댓값이 양수인 날이 여러 개면 가장 이른 날을 출력한다. 모든 날에 상자가 남지 않으면 0 0을 출력한다.

5
7 2
1 3
6 2
0 0
0 8

3 7

3
0 0
4 7
2 2

0 0

4
3 0
0 5
3 0
0 0

1 3

출처: Devin.KR 자체 제작