농장의 사료 통

문제

한 농장에서는 사료 통 하나를 사용하여 매일 들어오는 사료와 동물에게 나누어 주는 사료를 관리한다. 사료 통에 담을 수 있는 양은 최대 C단위이며, 첫날 아침에는 통이 비어 있다. 농장 관리자는 앞으로 N일 동안 들어올 사료의 양과 그날 필요한 사료의 양을 알고 있다. 이 계획을 실제 운영 순서대로 처리한 결과를 계산하려 한다. 하루의 작업은 반드시 입고, 넘친 사료 처리, 배급의 순서로 진행한다. 먼저 그날 들어온 사료를 전날 남아 있던 사료에 더한다. 이때 합이 C를 넘으면 C단위만 통에 남기고 나머지는 모두 버린다. 버린 사료를 통 밖에 보관하거나 그날의 배급에 사용하는 일은 없다. 입고량이 0이어도 이 단계는 같은 규칙으로 처리한다. 넘친 사료를 처리한 다음에는 동물에게 그날 필요한 양만큼 사료를 배급한다. 통 안의 사료가 필요한 양 이상이면 필요한 양을 정확히 꺼내고 남은 사료를 보관한다. 통 안의 사료가 필요한 양보다 적으면 남은 사료를 전부 꺼낸다. 이때 필요한 양에서 실제로 꺼낸 양을 뺀 만큼을 그날의 부족량으로 기록한다. 사료 통에 음수만큼의 사료가 남는 일은 없다. 그날 배급이 끝나고 남은 사료는 손실 없이 다음 날로 넘어간다. 부족량은 기록에만 남으며, 다음 날 더 배급해야 할 양으로 이월되지 않는다. 하루에 사료가 넘쳐 버려진 뒤 같은 날 사료가 부족해지는 경우도 가능하다. 이는 넘친 사료를 먼저 버리고 나서 배급하기 때문이다. 마지막 날 배급이 끝난 뒤에는 별도의 작업을 하지 않는다. 농장 관리자가 원하는 값은 마지막 날 작업 후 통에 남은 사료의 양, N일 동안 버린 사료의 총량, N일 동안 발생한 부족량의 총합이다. 각 날짜의 입고량과 필요량을 읽고 이 세 값을 구하는 프로그램을 작성한다.

입력

첫째 줄에 날짜 수 N과 사료 통의 용량 C가 공백으로 구분되어 주어진다. 다음 N개 줄 중 i번째 줄에 i번째 날의 입고량 S_i와 필요량 D_i가 공백으로 구분되어 주어진다. 모든 입력값은 정수이며 1≤N≤30,000, 1≤C≤1,000,000,000, 0≤S_i,D_i≤1,000이다.

출력

마지막 날 배급 후 남은 사료의 양, 전체 기간에 버린 사료의 총량, 전체 기간의 부족량 합을 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 버린 사료나 부족량이 없으면 해당 값으로 0을 출력한다.

4 7
10 3
1 6
9 2
0 8

0 5 4

3 5
0 0
0 2
4 1

3 0 2

1 2
5 4

0 3 2

출처: Devin.KR 자체 제작