주차권 판매 취소 정산

문제

한 주차장은 안내 창구에서 일회용 주차권을 묶음으로 판매한다. 백엔드 담당자는 창구의 요청 기록을 순서대로 처리하여 주차권 재고와 순매출을 계산하는 기능을 구현해야 한다. 주차권 한 장의 가격은 하루 동안 P원으로 고정되며, 업무 시작 시 판매할 수 있는 주차권은 K장이고 순매출은 0원이다. 요청에는 구매와 취소가 있다. 모든 요청에는 입력에 등장한 순서대로 1번부터 N번까지 번호를 붙인다. 이 번호는 요청의 성공 여부와 관계없이 부여한다. 따라서 실패한 구매나 취소 요청에도 번호가 있다. 구매 요청은 1 q로 나타내며, 주차권 q장을 한 번에 구매하겠다는 뜻이다. 현재 재고가 q장 이상이면 구매가 성공한다. 이때 재고에서 q장을 빼고 순매출에 q 곱하기 P원을 더한다. 재고가 부족하면 요청 전체가 실패한다. 일부 수량만 판매하지 않으며, 실패한 구매는 재고와 순매출에 영향을 주지 않는다. 취소 요청은 2 r로 나타내며, 번호가 r인 과거 요청을 취소하겠다는 뜻이다. 해당 요청이 성공한 구매이고 아직 취소되지 않았다면 취소가 성공한다. 이때 그 구매에서 판매한 주차권을 모두 재고로 돌려놓고, 당시 결제한 금액 전부를 순매출에서 뺀다. 부분 취소는 허용하지 않는다. 이미 취소된 구매, 실패한 구매, 취소 요청 자체를 대상으로 하면 이번 취소는 실패한다. 주차권은 실제 사용 전에만 이 기록에 등장하므로 성공한 구매의 취소를 추가 조건 없이 허용한다. 취소로 돌아온 주차권은 이후 구매에 즉시 사용할 수 있다. 실패한 취소도 재고와 순매출을 바꾸지 않는다. 구매 실패와 취소 실패는 모두 실패한 요청 수에 하나씩 포함한다. 모든 요청을 처리한 후 재고, 순매출, 실패한 요청 수를 계산한다.

입력

첫째 줄에 요청 수 N, 초기 재고 K, 주차권 한 장의 가격 P가 공백으로 구분되어 주어진다. N은 1 이상 40,000 이하, K는 0 이상 100,000 이하, P는 1 이상 1,000,000 이하의 정수다. 다음 N개 줄에 요청이 하나씩 주어진다. 구매 요청은 1 q이며 q는 1 이상 1,000 이하의 정수다. i번째 요청이 취소 요청이면 2 r 형태이며 r은 1 이상 i 미만의 정수다. 따라서 첫 번째 요청은 항상 구매 요청이다.

출력

최종 재고, 최종 순매출, 실패한 요청 수를 공백으로 구분하여 한 줄에 출력한다. 금액은 원 단위 정수로 출력하며, 각 값이 0이면 그대로 0을 출력한다.

7 5 100
1 3
1 4
2 1
1 5
2 1
2 2
2 4

5 0 3

5 4 250
1 2
1 2
2 1
2 3
1 1

1 750 1

1 0 1000000
1 1

0 0 1

출처: Devin.KR 자체 제작