주차 기록판의 첫 최고치

문제

한 주차장에서는 정해진 시간마다 차량의 이동을 묶어서 기록한다. 주차장은 기록을 시작할 때 비어 있으며, 이후 N개의 기록을 차례대로 처리한다. 각 기록에는 그 차례에 나간 차량 수와 들어온 차량 수가 적혀 있다. 한 기록을 처리할 때에는 먼저 적힌 수만큼 차량이 나간 뒤, 새 차량이 들어온다. 기록에 적히지 않은 차량 이동은 없다. 관리자는 기록판에 표시할 최고 주차 대수와 그 대수를 처음 확인한 기록 번호를 구하려고 한다. 기록 번호는 입력 순서대로 1번부터 N번까지다. 확인은 각 기록에서 차량이 모두 나가고 들어오는 과정이 끝난 직후에 한 번씩 한다. 기록을 시작하기 전의 빈 주차장도 0번 확인으로 취급하며, 이때 주차된 차량 수는 0대다. 최고 주차 대수는 0번부터 N번까지 확인한 차량 수 중 가장 큰 값이다. 같은 최고 대수가 여러 번 확인되었다면 가장 작은 기록 번호를 선택한다. 따라서 모든 확인에서 주차된 차량이 0대였다면 최고 대수는 0이고, 이를 처음 확인한 번호도 0이다. 차량이 나가는 단계와 들어오는 단계 사이의 상태는 별도의 확인으로 세지 않는다. 각 기록의 출차 대수와 입차 대수는 모두 0 이상 1,000 이하의 정수다. 출차 대수는 해당 기록을 처리하기 직전에 주차되어 있는 차량 수를 넘지 않는다. 주차장은 입력에 등장하는 차량을 모두 수용할 만큼 넓으므로 빈자리 부족으로 입차하지 못하는 차량은 없다. 주어진 순서대로 모든 기록을 처리하여, 기록판에 표시할 최고 주차 대수와 그 대수를 처음 확인한 번호를 출력한다.

입력

첫째 줄에 기록 수 N이 주어진다. (1 ≤ N ≤ 1,000)
다음 N개 줄의 i번째 줄에 i번 기록의 출차 대수 D_i와 입차 대수 E_i가 공백으로 구분되어 주어진다. (0 ≤ D_i, E_i ≤ 1,000)
주차장은 처음에 비어 있다. 모든 기록에서 D_i는 해당 기록 처리 직전의 주차 대수 이하임이 보장된다.
입력의 모든 수는 정수다.

출력

첫째 줄에 최고 주차 대수와 이를 처음 확인한 기록 번호를 공백으로 구분하여 출력한다. 시작 전 상태를 선택한다면 기록 번호로 0을 출력한다.

5
0 4
1 3
3 0
0 3
6 1

6 2

3
0 0
0 0
0 0

0 0

4
0 2
2 5
4 1
0 7

9 4

출처: Devin.KR 자체 제작