지원 요청 마감 일지

문제

한 회사의 IT 지원팀은 매일 들어오는 지원 요청을 처리하고, 업무를 마친 뒤 남은 요청 수를 일지에 적는다. 분석 대상 기간은 연속된 N일이며, 첫날 아침에는 이전 기간에서 넘어온 요청이 하나도 없다. 각 요청은 하나의 단위로 세며, 처리 중인 요청을 다음 날에 반만 넘기는 일은 없다. i번째 날 아침에는 새로운 요청 a_i개가 한꺼번에 접수된다. 그날 처리할 수 있는 요청 수의 상한은 b_i개이다. 지원팀은 전날 마감 후 남은 요청과 아침에 새로 접수된 요청을 합친 뒤, 그중 가능한 한 많은 요청을 처리한다. 따라서 요청이 충분하면 정확히 b_i개를 처리하고, 요청이 b_i개보다 적으면 있는 요청을 모두 처리한다. 새로 접수된 요청도 그날 바로 처리할 수 있다. 하루가 끝났을 때 처리되지 않은 요청은 모두 다음 날로 넘어간다. 접수된 요청이 취소되거나 저절로 사라지는 일은 없다. 반대로 처리할 요청이 부족해서 사용하지 못한 처리 가능 수는 다음 날로 넘기지 않는다. 예를 들어 요청이 2개 있을 때 처리 가능 수가 5개라면, 그날의 처리 수는 2이고 마감 후 남은 요청 수는 0이다. 지원팀은 기간 전체의 처리 실적과 가장 바빴던 마감 시점을 확인하려 한다. 이를 위해 N일 동안 실제로 처리한 요청 수의 합, 하루 마감 후 남은 요청 수의 최댓값, 그리고 그 최댓값이 처음 나타난 날짜를 구한다. 날짜는 첫날부터 1, 2, ..., N으로 센다. 마감 후 남은 요청 수는 매일 업무를 모두 마친 직후에만 비교하며, 아침이나 업무 도중의 요청 수는 비교하지 않는다. 모든 날의 마감 후 남은 요청 수가 0이라면 최댓값은 0이고 해당 날짜는 1이다. 마지막 날에 남은 요청은 처리 실적에 포함하지 않는다.

입력

첫째 줄에 날짜 수 N이 주어진다. 1 ≤ N ≤ 30,000이다.
다음 N개의 줄 중 i번째 줄에 정수 a_i와 b_i가 공백으로 구분되어 주어진다. 각각 i번째 날 새로 접수된 요청 수와 그날 처리 가능한 요청 수의 상한이다. 0 ≤ a_i, b_i ≤ 999이다.

출력

기간 전체에서 실제로 처리한 요청 수의 합, 마감 후 남은 요청 수의 최댓값, 그 최댓값이 처음 나타난 날짜를 공백으로 구분하여 한 줄에 출력한다.

4
4 1
2 4
0 3
5 2

8 3 1

1
0 0

0 0 1

3
3 0
0 1
4 0

1 6 3

출처: Devin.KR 자체 제작