호텔 예약 장부 마감

문제

한 호텔의 백엔드 담당자는 예약 요청과 취소 요청을 순서대로 처리한 뒤 객실 재고와 정산 금액을 마감하려 한다. 객실 유형은 1번부터 M번까지이며, 유형마다 처음 판매할 수 있는 객실 수와 객실 한 개의 1박 가격이 정해져 있다. 모든 예약은 같은 날에 입실한다. 요청을 처리하는 동안 실제 입실이나 퇴실은 일어나지 않으므로, 숙박 일수와 관계없이 예약한 객실 수만큼 해당 유형의 재고를 점유한다. 요청에는 입력 순서대로 1번부터 N번까지 번호를 붙인다. 예약 요청 B t q d는 t번 유형의 객실 q개를 각각 d박 동안 예약한다는 뜻이다. 현재 해당 유형의 재고가 q개 이상이면 요청을 승인하고 재고에서 q를 뺀다. 이때 q × d × 해당 유형의 1박 가격을 전액 결제받아 정산 금액에 더한다. 재고가 부족하면 요청 전체를 거절하며 재고와 정산 금액을 바꾸지 않는다. 일부 객실만 예약하는 처리는 하지 않는다. 취소 요청 C k는 k번 요청으로 승인된 예약을 취소한다는 뜻이다. k번 요청이 승인되었고 아직 취소되지 않은 예약이면 해당 객실을 모두 재고에 돌려놓는다. 또한 그 예약의 최초 결제 금액을 A라고 할 때, A의 80퍼센트를 넘지 않는 가장 큰 정수 금액을 환불하여 정산 금액에서 뺀다. 남은 금액은 취소 수수료로 유지한다. 객실 일부만 취소하는 요청은 없다. k번 요청이 거절된 예약이거나 취소 요청이거나 이미 취소된 예약이면 해당 취소 요청을 무시한다. 취소로 돌아온 객실은 이후 예약에서 다시 판매할 수 있다. 가격은 처리 도중 변하지 않으며 정산 금액은 0에서 시작한다. 모든 요청을 처리한 뒤 승인 상태로 남아 있는 예약 요청의 개수, 최종 정산 금액, 유형별 남은 객실 수를 구한다.

입력

첫째 줄에 정수 M과 N이 주어진다. 1 ≤ M ≤ 100, 1 ≤ N ≤ 10,000이다.
다음 M개 줄의 t번째 줄에 t번 유형의 초기 재고 S_t와 1박 가격 P_t가 주어진다. 0 ≤ S_t ≤ 1,000, 1 ≤ P_t ≤ 1,000,000,000이며 모두 정수다.
다음 N개 줄에 요청이 하나씩 주어진다. 예약 요청은 B t q d 형식이며 1 ≤ t ≤ M, 1 ≤ q ≤ 1,000, 1 ≤ d ≤ 30이다. 취소 요청은 C k 형식이며, 현재 요청 번호가 i일 때 1 ≤ k < i다. 따라서 첫 번째 요청은 항상 예약 요청이다. 모든 수는 정수다.

출력

첫째 줄에 취소되지 않은 승인 예약 요청의 개수와 최종 정산 금액을 공백으로 구분하여 출력한다. 예약 개수는 객실 수가 아니라 요청 수를 센다. 둘째 줄에 1번 유형부터 M번 유형까지의 남은 객실 수를 공백으로 구분하여 출력한다. 남아 있는 예약이나 정산 금액이 없으면 해당 값으로 0을 출력한다.

2 6
3 101
1 200
B 1 2 2
B 1 2 1
C 1
B 1 3 1
C 1
B 2 1 2

2 784
0 0

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

0 0
0

1 3
1 7
B 1 1 1
C 1
C 1

0 2
1

출처: Devin.KR 자체 제작