항공권 창구의 처리 기록

문제

한 항공편의 예약 창구는 항공권 번호를 이용하여 예약과 취소 요청을 처리한다. 항공편에는 총 C개의 좌석이 있으며, 처음에는 예약된 좌석이 없다. 좌석의 위치는 구분하지 않고 예약된 좌석 수만 관리한다. 항공권 번호 하나에는 동시에 최대 한 건의 예약만 연결할 수 있다. 요청은 입력에 주어진 순서대로 하나씩 처리한다. 종류가 1인 요청은 해당 항공권 번호로 좌석 하나를 예약하라는 뜻이다. 그 번호에 이미 예약이 있거나 모든 좌석이 예약된 상태라면 요청을 무시한다. 두 조건이 동시에 성립하더라도 무시한 요청 수는 한 번만 늘린다. 그렇지 않으면 예약을 확정하고 그때의 판매 금액을 해당 항공권 번호에 저장한다. 예약 직전에 예약된 좌석 수를 x라고 하자. 새로 예약하는 항공권의 판매 금액은 P + floor(x / K) × D이다. floor(x / K)는 x를 K로 나눈 몫을 뜻한다. 따라서 예약이 늘어나면 새 항공권의 가격이 높아질 수 있으며, 취소로 예약 수가 줄어들면 이후에 판매하는 항공권의 가격이 다시 낮아질 수 있다. 이미 확정된 예약에 저장한 판매 금액은 다른 요청 때문에 바뀌지 않는다. 종류가 2인 요청은 해당 번호의 예약을 취소하라는 뜻이다. 그 번호에 예약이 없다면 요청을 무시한다. 예약이 있다면 좌석 하나를 비우고 그 예약을 확정할 때 저장했던 판매 금액 전부를 환불한다. 취소한 항공권 번호는 이후에 다시 예약할 수 있으며, 이때는 새로운 판매 금액을 저장한다. 모든 요청을 처리한 뒤 남은 예약 수와 순수입, 그리고 무시한 요청 수를 구해야 한다. 순수입은 확정된 예약의 판매 금액 합에서 취소된 예약의 환불 금액 합을 뺀 값이다. 처음 순수입은 0이다. 모든 요청이 무시되거나 모든 예약이 취소되어도 같은 규칙에 따라 결과를 출력한다.

입력

첫째 줄에 C, P, K, D, M이 공백으로 구분되어 주어진다. 모두 정수이며 1 ≤ C ≤ 9,999, 1 ≤ P ≤ 1,000,000, 1 ≤ K ≤ C, 0 ≤ D ≤ 1,000,000, 1 ≤ M ≤ 50,000이다.
다음 M개 줄에 요청 종류 T와 항공권 번호 A가 주어진다. T는 1 또는 2이며, A는 1 이상 9,999 이하의 정수이다.

출력

모든 요청을 처리한 뒤 남은 예약 수, 순수입, 무시한 요청 수를 공백으로 구분하여 한 줄에 출력한다. 순수입은 정수로 출력한다.

3 100 1 20 7
1 10
1 20
1 10
2 10
1 30
2 99
1 40

3 380 2

1 50 1 7 5
2 1
1 2
1 3
2 2
2 2

0 0 3

4 30 2 5 4
1 1
1 2
1 3
2 1

2 65 0

출처: Devin.KR 자체 제작