택배 출고 대기 장부

문제

택배 출고 서버는 한 종류의 상품을 취급하는 창고의 주문 장부를 관리한다. 처음에는 아직 출고되지 않은 상품 S개가 있고, 출고 대기 중인 주문은 없다. 서버는 상품 가운데 새 주문에 배정할 수 있는 수량을 가용 재고로 관리한다. 처음 가용 재고는 S개다. 주문을 접수하면 상품을 미리 확보하므로 가용 재고가 줄어들지만, 실제 출고는 나중에 별도 이벤트가 도착했을 때 이루어진다. 서버에 전달되는 이벤트는 A, D, C의 세 종류다. 모든 이벤트는 입력에 적힌 순서대로 하나씩 처리한다. A I Q P는 주문 번호 I로 상품 Q개를 접수하려는 이벤트이며, P는 이 주문의 상품 한 개당 정산 금액이다. 같은 번호의 출고 대기 주문이 이미 있거나 현재 가용 재고가 Q개보다 적다면 이 이벤트 전체를 무시한다. 두 조건에 모두 해당하지 않으면 주문을 출고 대기 상태로 등록하고 가용 재고에서 Q개를 뺀다. 일부 수량만 접수하는 일은 없다. D I는 주문 번호 I의 상품을 출고하는 이벤트다. 해당 번호의 출고 대기 주문이 있으면 접수 때 저장한 Q와 P를 사용하여 정산 누계에 Q × P를 더하고 그 주문을 장부에서 제거한다. 상품은 접수할 때 이미 확보했으므로 출고 시 가용 재고는 바꾸지 않는다. 해당 주문이 없다면 이벤트를 무시한다. C I는 주문 번호 I의 접수를 취소하는 이벤트다. 해당 번호의 출고 대기 주문이 있으면 확보해 두었던 Q개를 가용 재고에 돌려놓고 그 주문을 장부에서 제거한다. 취소는 정산 누계를 바꾸지 않는다. 해당 주문이 없다면 이 이벤트 역시 무시한다. 출고하거나 취소하여 장부에서 제거한 주문 번호는 이후의 A 이벤트에서 다시 사용할 수 있다. 거절된 A 이벤트가 주문 번호를 차지하는 일도 없다. 정산 누계는 처음에 0이며, 출고가 완료된 금액만 포함한다. 출고 대기 주문의 예상 금액은 포함하지 않는다. 모든 이벤트를 처리한 뒤 가용 재고, 출고 대기 주문 건수, 정산 누계를 구한다. 장부에서 이미 제거된 주문에 대한 이벤트도 주어질 수 있으므로, 각 이벤트의 처리 여부는 그 시점의 장부를 기준으로 결정해야 한다.

입력

첫째 줄에 초기 재고 S와 이벤트 수 N이 공백으로 구분되어 주어진다. S는 0 이상 1,000,000 이하의 정수이며, N은 1 이상 15,000 이하의 정수다.
다음 N개 줄에 이벤트가 하나씩 주어진다. 형식은 A I Q P, D I, C I 중 하나다.
I는 1 이상 10,000 이하, Q는 1 이상 1,000 이하, P는 1 이상 1,000,000 이하의 정수다. 모든 이벤트의 값은 이 범위에 속하며, 처리할 수 없어 무시되는 이벤트도 입력에 포함될 수 있다.

출력

모든 이벤트를 처리한 뒤의 가용 재고, 출고 대기 주문 건수, 정산 누계를 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 세 값은 모두 정수다. 출고된 주문이 없다면 정산 누계는 0이다.

10 9
A 4 6 100
A 4 1 900
A 8 5 20
D 4
A 8 4 30
C 8
A 4 3 50
D 8
D 4

1 0 750

0 4
A 1 1 10
D 1
C 1
A 1 2 20

0 0 0

8 5
A 2 3 7
A 5 2 9
C 2
A 2 4 11
D 5

2 1 18

출처: Devin.KR 자체 제작