정차 뒤의 승객 기록

문제

한 지하철 열차가 승객이 없는 상태로 출발하여 N개의 역에 차례대로 정차한다. 운행 기록에는 각 역에서 내린 승객 수와 탄 승객 수가 적혀 있다. 기록을 확인하는 담당자는 각 역에서 승객의 이동이 모두 끝난 직후 열차 안에 남은 승객 수를 구하려 한다. 역에는 방문한 순서대로 1번부터 N번까지 번호가 붙어 있다. 각 역에서는 내릴 승객이 먼저 모두 내린 뒤, 탈 승객이 모두 탄다. i번 역에서 내리는 승객 수를 A_i, 타는 승객 수를 B_i라고 한다. A_i는 그 역에 도착했을 때 열차 안에 있는 승객 수를 넘지 않는다. 따라서 기록을 순서대로 처리하면 열차 안의 승객 수가 음수가 되는 일은 없다. 마지막 역에서도 승객이 남아 있을 수 있으며, 모든 승객이 내려야 한다는 조건은 없다. 담당자는 이 기록으로 세 가지 값을 작성한다. 첫 번째 값은 각 역에서 승객의 이동이 모두 끝난 직후의 승객 수 중 최댓값이다. 두 번째 값은 그 최댓값을 처음 기록한 역의 번호이다. 같은 최댓값을 여러 역에서 기록했다면 번호가 가장 작은 역을 선택한다. 세 번째 값은 모든 역에서 승객의 이동이 끝난 직후의 승객 수를 각각 한 번씩 더한 합이다. 세 번째 값은 서로 다른 승객의 수를 뜻하지 않는다. 한 승객이 여러 역을 계속 지나면 해당 승객은 그 역들의 기록에 반복해서 포함된다. 출발 전 승객 수인 0은 합에 따로 더하지 않으며, N번 역의 승객 수는 합에 포함한다. 또한 첫 번째 값은 역 사이의 변화나 하차 직후의 상태가 아니라 승차까지 모두 끝난 상태만 비교하여 구한다. 모든 역의 기록이 0명이라면 최댓값은 0이고 이를 처음 기록한 역은 1번 역이다. 운행 기록을 읽고 세 값을 구하는 프로그램을 작성한다.

입력

첫째 줄에 역의 수 N이 주어진다. 다음 N개 줄 중 i번째 줄에 A_i와 B_i가 공백으로 구분되어 주어진다. 모든 입력값은 정수이며 1≤N≤30,000, 0≤A_i,B_i≤1,000이다. A_i는 i번 역에 도착했을 때의 승객 수 이하임이 보장된다. 열차는 승객이 없는 상태에서 시작한다.

출력

최대 승객 수, 그 최댓값을 처음 기록한 역의 번호, 각 역에서 승객의 이동이 끝난 직후의 승객 수를 모두 더한 값을 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 합은 32비트 부호 있는 정수의 범위를 넘을 수 있다.

5
0 4
1 2
3 0
0 3
5 1

5 2 17

3
0 0
0 0
0 0

0 1 0

1
0 7

7 1 7

출처: Devin.KR 자체 제작