편의점 진열대의 부족 수량

문제

한 편의점에서 한 종류의 음료를 판매한다. 점원은 일정 기간 동안 진열대의 재고와 판매하지 못한 수량을 기록하려고 한다. 첫날 영업을 시작하기 전 진열대에는 S개의 음료가 있으며, 날짜별로 입고 수량과 손님들이 구매하려는 수량이 주어진다. 진열대의 크기에는 제한이 없고, 음료는 기간 중 변질되거나 다른 이유로 사라지지 않는다. 하루의 처리는 반드시 입고, 판매 순서로 진행한다. 먼저 그날 입고된 음료를 모두 진열대에 더한다. 그다음 손님들이 구매하려는 수량만큼 음료를 판매한다. 재고가 충분하면 요청한 수량을 전부 판매한다. 재고가 부족하면 남은 음료를 전부 판매하고 재고는 0개가 된다. 이때 구매하려는 수량에서 실제 판매한 수량을 뺀 값을 그날의 부족 수량이라고 한다. 재고가 충분한 날의 부족 수량은 0이다. 판매하지 못한 요청은 그날로 끝난다. 부족 수량을 다음 날의 구매 요청에 더하지 않으며, 다음 날 입고된 음료로 이전 요청을 처리하지도 않는다. 반면 판매하고 남은 음료는 그대로 다음 날로 넘어간다. 입고 수량이나 구매하려는 수량이 0인 날에도 같은 규칙을 적용한다. 모든 날짜를 차례대로 처리한 뒤 마지막 날 판매가 끝났을 때 남은 재고와, 전체 기간의 부족 수량 합계를 구한다. 또한 하루 부족 수량이 가장 컸던 날짜를 구한다. 날짜는 입력 순서대로 1일부터 N일까지 번호를 붙인다. 가장 큰 부족 수량이 같은 날이 여러 날이면 가장 이른 날짜를 선택한다. 모든 날의 부족 수량이 0이면 선택한 날짜 대신 0을 사용한다. 날짜를 선택할 때에는 입고 수량이나 남은 재고를 비교하지 않고 오직 그날의 부족 수량만 비교한다.

입력

첫째 줄에 정수 N과 S가 주어진다. 1 ≤ N ≤ 30,000이며 0 ≤ S ≤ 999다.
다음 N개 줄의 i번째 줄에 i일의 입고 수량 A_i와 구매하려는 수량 B_i가 주어진다. A_i와 B_i는 각각 0 이상 999 이하의 정수다.

출력

마지막 재고, 전체 부족 수량의 합, 선택한 날짜를 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 모든 값은 정수다.

4 2
1 5
4 1
0 5
2 1

1 4 1

3 0
0 0
5 2
0 3

0 0 0

3 0
0 1
0 4
2 6

0 9 2

출처: Devin.KR 자체 제작