대여소 마감 기록

문제

공유 자전거 운영팀은 한 대여소의 자전거 수를 시간 구간별로 정리한다. 데이터 담당자가 받은 표에는 각 구간에 대여된 자전거 수와 반납된 자전거 수가 기록되어 있다. 표의 행은 실제 시간 순서대로 주어지며, 첫 번째 행이 가장 이른 구간이다. 운영팀은 이 표를 바탕으로 마지막 구간이 끝났을 때 남은 자전거 수와 자전거가 가장 적었던 점검 시점을 보고하려 한다. 첫 구간이 시작되기 전에 대여소에 있는 자전거 수는 S대이다. 각 행을 처리할 때에는 먼저 그 행의 대여 대수만큼 현재 자전거 수를 줄이고, 이어서 반납 대수만큼 늘린다. 모든 행에서 대여 대수는 그 행을 처리하기 직전의 자전거 수 이하이다. 따라서 표를 처리하는 도중 자전거 수가 음수가 되는 경우는 없다. 반납되는 자전거는 다른 대여소에서 빌린 것일 수도 있으므로 반납 대수가 대여 대수보다 클 수 있다. 운영팀이 비교하는 점검 시점은 시작 전과 각 구간이 모두 끝난 직후뿐이다. 시작 전의 번호는 0이고, i번째 행을 처리한 직후의 번호는 i이다. 한 구간에서 대여를 처리한 뒤 반납을 처리하기 전의 자전거 수는 점검 대상이 아니다. 따라서 대여와 반납이 같은 구간에 있었다면 두 수를 모두 반영한 결과만 비교한다. 총 N+1개의 점검 시점 중 자전거 수가 가장 적은 시점을 찾는다. 같은 최솟값이 여러 번 나타나면 번호가 가장 작은 시점을 선택한다. 시작 전부터 자전거가 가장 적었다면 선택할 번호는 0이다. 입력 표는 머리글 없이 쉼표로 두 열을 구분하며 쉼표 앞뒤에 공백은 없다. 마지막 자전거 수, 점검 시점의 최소 자전거 수, 선택한 시점 번호를 차례로 구한다.

입력

첫 줄에 정수 N과 S가 공백으로 구분되어 주어진다. 1≤N≤1,000, 0≤S≤1,000이다.
다음 N개 줄에는 정수 D,R이 쉼표로 구분되어 주어진다. D는 해당 구간의 대여 대수이고 R은 반납 대수이다. 0≤D,R≤1,000이다. 각 행의 D는 그 행을 처리하기 직전의 자전거 수 이하임이 보장된다. 머리글과 빈 줄은 없다.

출력

마지막 구간 직후의 자전거 수, 모든 점검 시점에서의 최소 자전거 수, 그 최솟값이 처음 나타난 시점 번호를 공백으로 구분하여 한 줄에 출력한다. 시작 전의 시점 번호는 0이다.

4 8
5,1
2,0
0,5
6,1

2 2 2

3 0
0,4
4,0
0,0

0 0 0

1 5
5,5

5 5 0

출처: Devin.KR 자체 제작