택배 분류대의 마감 기록

문제

작은 택배 작업장에서는 매일 아침 도착한 택배를 분류대에 올리고, 그날의 작업이 끝날 때까지 가능한 만큼 분류한다. 작업을 시작하는 첫날 아침에는 이전 날짜에서 넘어온 택배가 하나도 없다. 이후에는 전날 분류하지 못한 택배를 그대로 남겨 두었다가 다음 날 아침 새로 도착한 택배와 함께 처리한다. 택배가 도착하는 시각은 모두 아침 작업 시작 전이며, 작업 중간에 추가로 도착하는 택배는 없다. 하루에 분류할 수 있는 택배 수는 작업 인원과 장비 상태에 따라 달라진다. 어떤 날 아침에 분류대에 놓인 택배 수가 그날의 처리 가능 개수보다 많으면, 처리 가능 개수만큼 분류하고 나머지를 남긴다. 반대로 놓인 택배 수가 처리 가능 개수 이하이면 전부 분류한다. 사용하지 못한 처리 능력은 그날 사라지며, 다음 날 더 많은 택배를 분류하는 데 사용할 수 없다. 이미 분류한 택배는 즉시 다른 장소로 옮기므로 이후 기록에 다시 포함되지 않는다. 관리자는 N일 동안 매일 새로 도착한 택배 수와 그날 분류할 수 있는 최대 개수를 기록했다. 관리자가 말하는 마감 잔량은 그날의 분류 작업을 모두 끝낸 직후 분류대에 남은 택배 수이다. 아침에 택배가 많이 쌓였더라도 그날 전부 분류했다면 마감 잔량은 0이다. 기록에 있는 모든 개수는 실제 택배의 개수를 나타내는 정수이다. 이 기록을 날짜순으로 적용하여 마지막 날의 마감 잔량을 구한다. 또한 전체 기록에서 마감 잔량이 가장 많았던 날짜도 구한다. 같은 최대 잔량을 기록한 날짜가 여러 개면 가장 이른 날짜를 선택한다. 모든 날의 마감 잔량이 0인 경우에도 날짜를 하나 선택해야 하며, 이때는 첫날인 1일을 선택한다.

입력

첫째 줄에 기록한 날짜 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 1,000이다.
다음 N개 줄에는 해당 날짜에 새로 도착한 택배 수 A_i와 그날 분류할 수 있는 최대 개수 C_i가 공백으로 주어진다. 줄은 1일부터 N일까지 날짜순으로 주어진다. 모든 A_i와 C_i는 정수이며 0 ≤ A_i, C_i ≤ 1,000이다.

출력

마지막 날의 마감 잔량과 마감 잔량이 가장 많았던 날짜를 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 최대 잔량을 기록한 날짜가 여러 개면 가장 이른 날짜를 출력한다.

4
8 3
1 4
7 2
0 5

2 3

3
2 5
0 0
4 4

0 1

3
5 1
2 2
0 1

3 1

출처: Devin.KR 자체 제작