급식 추가 배식 주문 처리

문제

한 학교의 급식실에서는 기본 배식을 마친 뒤 남은 식사를 추가 배식 창구에서 판매한다. 급식 관리 서비스의 백엔드는 조리실에서 도착하는 보충 기록과 창구에서 들어오는 주문 기록을 하나의 시간순 목록으로 전달받는다. 담당자는 이 목록을 처리하여 최종 재고와 판매 정산 결과를 계산하려 한다. 처리를 시작할 때 판매 가능한 식사는 S인분이고, 한 인분의 판매 가격은 P원이다. 가격은 모든 기록을 처리하는 동안 바뀌지 않는다. 기록은 두 종류이며, 각 기록에는 종류를 나타내는 정수와 양의 정수 X가 들어 있다. 종류가 1이면 조리실에서 식사 X인분을 보충한 기록이다. 이 기록을 처리할 때 현재 재고에 X를 더한다. 보충 자체로 판매 금액이 발생하지는 않는다. 종류가 2이면 식사 X인분을 한꺼번에 구매하려는 주문이다. 주문을 처리하는 순간의 재고가 X 이상이면 주문 전체를 승인한다. 승인한 경우 재고에서 X를 빼고, 판매 수량에 X를 더하며, 판매 금액에 X 곱하기 P원을 더한다. 재고가 X보다 적으면 주문 전체를 거절한다. 일부 수량만 판매하는 일은 없으며, 거절한 주문은 재고와 판매 금액을 바꾸지 않는다. 기록은 입력에 주어진 순서대로 하나씩 처리한다. 앞선 주문이 거절되었더라도 뒤에서 재고가 보충되면 뒤의 주문은 승인될 수 있다. 거절한 주문을 보관했다가 나중에 다시 처리하지는 않는다. 주문 취소나 환불은 없고, 승인한 주문은 모두 즉시 결제가 끝난 것으로 본다. 모든 기록을 처리한 뒤 남은 재고, 승인한 주문의 총판매 수량, 총판매 금액, 거절한 주문 건수를 구한다. 거절 건수는 부족했던 인분 수가 아니라 거절된 종류 2 기록의 개수다. 판매나 거절이 한 번도 없었다면 해당 결과는 0이다.

입력

첫째 줄에 정수 N, S, P가 공백으로 구분되어 주어진다. N은 기록 수이고, S는 초기 재고이며, P는 한 인분의 가격이다. 1 ≤ N ≤ 40,000, 0 ≤ S ≤ 999,999, 1 ≤ P ≤ 10,000이다.
다음 N개 줄에 정수 T와 X가 공백으로 구분되어 주어진다. T는 1 또는 2이고, 1 ≤ X ≤ 999,999이다. 기록은 처리할 순서대로 주어진다.

출력

최종 재고, 총판매 수량, 총판매 금액, 거절한 주문 건수를 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 모든 값은 정수로 출력한다.

6 5 1200
2 3
2 4
1 6
2 4
2 4
2 1

0 11 13200 2

3 0 900
2 2
1 3
2 4

3 0 0 2

2 2 500
2 2
1 1

1 2 1000 0

출처: Devin.KR 자체 제작