창고의 마감 최고 기록

문제

물류 창고에서는 매일 작업을 마친 뒤 보관 중인 상자의 수를 기록한다. 관찰을 시작하기 직전에는 창고에 S개의 상자가 있다. 이 최초 상태를 0일의 기록이라고 부른다. 이후 1일부터 N일까지 하루에 한 번씩 그날의 입고 수와 출고 수를 확인하고 새로운 마감 기록을 만든다. 상자는 모두 개수로만 관리하며, 크기나 종류를 구분하지 않는다. 각 날짜에는 먼저 그날 들어오는 상자를 모두 창고에 넣고, 이어서 그날 나가는 상자를 모두 꺼낸다. i일의 입고 수가 Ai개이고 출고 수가 Bi개라면, 전날의 마감 상자 수에 Ai를 더하고 Bi를 뺀 값이 i일의 마감 상자 수가 된다. 입력은 매일 출고할 상자가 충분하도록 주어지므로, 작업 도중이나 마감 시점에 상자 수가 음수가 되는 경우는 없다. 관리자는 0일부터 N일까지의 기록 중 상자 수가 가장 많았던 마감 기록을 찾으려 한다. 하루 중 입고 직후의 상자 수는 비교 대상에 포함하지 않는다. 예를 들어 입고 직후 상자가 많이 쌓였더라도 같은 날 출고하여 마감 상자 수가 줄었다면, 줄어든 뒤의 수만 그날의 기록으로 사용한다. 0일에는 입고와 출고를 수행하지 않고 최초 상자 수 S 자체를 기록으로 사용한다. 최댓값이 여러 날짜에 나타나면 날짜 번호가 가장 작은 날을 선택한다. 따라서 모든 날의 마감 상자 수가 S와 같거나 그보다 작으면 선택되는 날은 0일이다. 입고 수와 출고 수가 모두 0인 날도 하나의 날짜로 계산하며, 그날의 기록을 생략하지 않는다. N일 동안의 입고 및 출고 기록이 주어질 때, 마지막 날의 마감 상자 수, 전체 마감 기록의 최댓값, 그리고 그 최댓값이 처음 나타난 날짜를 구하는 프로그램을 작성한다. 계산에 필요한 모든 값은 정수이며, 별도로 사라지거나 생기는 상자는 없다.

입력

첫째 줄에 정수 N과 S가 주어진다.
다음 N개 줄 중 i번째 줄에 정수 Ai와 Bi가 공백으로 구분되어 주어진다.
1 ≤ N ≤ 1,000, 0 ≤ S ≤ 1,000, 0 ≤ Ai, Bi ≤ 1,000이다. 각 날짜의 출고 수는 전날의 마감 상자 수와 그날의 입고 수를 더한 값 이하이다.

출력

N일의 마감 상자 수, 0일부터 N일까지 마감 상자 수의 최댓값, 그 최댓값이 처음 나타난 날짜 번호를 공백으로 구분하여 한 줄에 출력한다.

4 5
4 1
0 3
7 4
1 2

7 8 1

3 10
0 4
2 2
4 0

10 10 0

1 0
0 0

0 0 0

출처: Devin.KR 자체 제작