메신저 주문 장부

문제

사내 메신저의 공동 구매 채널에서 한 종류의 상품을 판매한다. 백엔드 담당자는 채널에 도착한 주문 메시지와 취소 메시지를 차례대로 처리하여 마지막 정산 장부를 만들어야 한다. 처음 판매할 수 있는 상품은 S개이며, 상품 한 개의 판매 가격은 P원이다. 처리 도중 추가 입고나 가격 변경은 없다. 메시지는 BUY와 CANCEL의 두 종류다. BUY i q는 주문 번호 i로 상품 q개를 주문한다는 뜻이다. 이 메시지를 처리하는 순간 남은 재고가 q개 이상이면 주문을 승인하고 재고에서 q개를 뺀다. 승인된 주문은 취소되기 전까지 유효한 주문으로 남는다. 재고가 부족하면 주문 전체를 거절하며, 일부 수량만 승인하지 않는다. 거절된 주문은 나중에 재고가 늘어나더라도 다시 심사하지 않는다. CANCEL i는 주문 번호 i의 취소 요청이다. 해당 번호가 현재 유효한 주문이면 그 주문 전체를 취소하고 주문 수량만큼 재고를 되돌린다. 아직 등장하지 않은 주문, 거절된 주문, 이미 취소된 주문에 대한 취소 요청은 아무 변화도 일으키지 않는다. 아직 등장하지 않은 번호를 취소하더라도 그 번호가 이후의 주문에 사용되는 것을 막지는 않는다. 각 BUY 메시지의 주문 번호는 다른 BUY 메시지의 주문 번호와 겹치지 않는다. 같은 번호의 CANCEL 메시지는 여러 번 등장할 수 있다. 메시지에는 별도의 시간이 없으며, 입력에 주어진 순서가 곧 처리 순서다. 따라서 재고를 두고 경쟁하는 주문의 우선순위도 이 순서로 정해진다. 모든 메시지를 처리한 뒤 유효한 주문 수, 남은 재고, 정산 금액을 구한다. 정산 금액은 유효한 주문들의 상품 수량 합에 P를 곱한 값이다. 거절되거나 취소된 주문은 정산에 포함하지 않으며, 수수료나 배송비는 없다. 유효한 주문이 하나도 없으면 주문 수와 정산 금액은 모두 0이다.

입력

첫째 줄에 메시지 수 N, 초기 재고 S, 상품 한 개의 가격 P가 공백으로 구분되어 주어진다. N, S, P는 정수이며 1 ≤ N ≤ 20,000, 0 ≤ S ≤ 1,000,000,000, 1 ≤ P ≤ 1,000,000이다.
다음 N개 줄에는 메시지가 하나씩 주어진다. 주문 메시지의 형식은 BUY i q이며, 취소 메시지의 형식은 CANCEL i이다. i와 q는 정수이며 1 ≤ i ≤ N, 1 ≤ q ≤ 1,000이다. 모든 BUY 메시지의 주문 번호 i는 서로 다르다. CANCEL 메시지의 번호에는 추가 제약이 없다. 명령어는 대문자로 주어진다.

출력

모든 메시지를 처리한 뒤 유효한 주문 수, 남은 재고, 정산 금액을 이 순서대로 한 줄에 공백으로 구분하여 정수로 출력한다.

8 10 700
BUY 1 6
BUY 2 5
CANCEL 2
CANCEL 1
BUY 3 7
CANCEL 1
BUY 4 2
CANCEL 8

2 1 6300

4 0 50
BUY 1 1
CANCEL 1
BUY 2 3
CANCEL 2

0 0 0

6 8 120
BUY 1 4
CANCEL 1
BUY 2 8
CANCEL 1
CANCEL 2
BUY 3 3

1 5 360

출처: Devin.KR 자체 제작