한정 이용권 주문 장부

문제

음악 스트리밍 서비스에서 한정 수량으로 판매하는 특별 이용권의 주문 장부를 처리한다. 판매를 시작할 때 남은 이용권은 S개이고, 이용권 한 개의 판매 가격은 P이다. 모든 주문에는 같은 가격을 적용하며 수수료나 추가 할인은 없다. 백엔드는 시간순으로 정리된 N개의 이벤트를 입력 순서대로 처리한다. 이벤트에는 구매 요청과 취소 요청이 있다. 구매 요청 B q는 이용권 q개를 한 번에 구매하려는 요청이다. 처리 시점의 남은 수량이 q 이상이면 구매가 성공한다. 성공한 경우 남은 수량에서 q를 빼고 정산 금액에 q × P를 더한다. 남은 수량이 부족하면 구매 전체가 실패한다. 일부 수량만 판매하는 일은 없으며, 실패한 구매는 수량과 정산 금액을 바꾸지 않는다. 각 이벤트에는 입력에서의 위치에 따라 1부터 N까지 번호를 붙인다. 성공 여부와 관계없이 구매 요청의 주문 번호는 그 구매 요청이 발생한 이벤트 번호이다. 취소 요청 C r은 이벤트 번호가 r인 구매 요청을 취소하려는 요청이다. 입력은 r번 이벤트가 현재보다 앞에 있는 구매 요청임을 보장한다. 취소 대상 구매가 성공했고 아직 취소되지 않았다면 취소가 성공한다. 이때 해당 구매의 수량 전부를 남은 수량에 돌려놓고, 그 구매에서 더했던 금액 전부를 정산 금액에서 뺀다. 실패한 구매를 취소하거나 이미 취소한 구매를 다시 취소하려는 요청은 아무 변화 없이 무시한다. 취소한 주문을 다시 활성화하는 기능은 없다. 취소로 돌아온 이용권은 그다음 구매 요청부터 다시 판매할 수 있다. 과거에 수량 부족으로 실패한 구매를 자동으로 재시도하지는 않는다. 정산 금액은 처음에 0이며, 취소되지 않은 성공 구매들의 결제 금액 합을 뜻한다. 모든 이벤트를 처리한 뒤 남은 이용권 수와 정산 금액을 구한다. 성공한 구매가 없거나 모든 성공 구매가 취소되었다면 정산 금액은 0이다.

입력

첫째 줄에 정수 S, P, N이 공백으로 구분되어 주어진다. 0 ≤ S ≤ 1,000,000,000, 1 ≤ P ≤ 1,000,000,000, 1 ≤ N ≤ 100,000이다.
다음 N개 줄에 이벤트가 하나씩 주어진다. 구매 요청은 B q이며 q는 1 ≤ q ≤ 1,000,000,000인 정수이다. 취소 요청은 C r이며 r은 1 ≤ r < 현재 이벤트 번호인 정수이다. r번 이벤트는 반드시 구매 요청이다. 같은 구매 요청을 여러 번 취소 대상으로 지정할 수 있다.

출력

모든 이벤트를 처리한 뒤 남은 이용권 수와 정산 금액을 한 줄에 공백으로 구분하여 정수로 출력한다.

5 120 7
B 4
B 2
C 1
B 3
C 2
C 1
B 2

0 600

0 50 3
B 1
C 1
C 1

0 0

1000000000 1000000000 3
B 1000000000
C 1
B 999999999

1 999999999000000000

출처: Devin.KR 자체 제작