배달 주문의 마감 정산

문제

배달 앱의 백엔드 담당자는 한 가게에서 발생한 주문 요청을 입력된 순서대로 처리하고, 마감 시점의 판매 대금을 계산하려 한다. 가게에는 M종류의 메뉴가 있으며 각 메뉴에는 1부터 M까지의 번호가 붙어 있다. 메뉴별 판매 단가와 영업 시작 시점의 재고가 주어진다. 한 요청은 한 종류의 메뉴만 다루며, 여러 메뉴를 묶어서 처리하는 요청은 없다. 요청 종류는 주문과 취소 두 가지이다. 주문 요청에는 메뉴 번호와 수량이 들어 있다. 요청 시점의 해당 메뉴 재고가 수량 이상이면 요청한 수량 전체를 판매하고 재고에서 그 수량을 뺀다. 재고가 부족하면 주문 전체를 거절한다. 일부 수량만 판매하지 않으며, 거절된 주문은 재고와 판매 대금에 아무 영향도 주지 않는다. 같은 메뉴에 대한 요청이라도 앞선 요청의 처리 결과가 뒤의 요청에 영향을 준다. 취소 요청에는 앞서 등장한 주문 요청의 번호가 들어 있다. 그 주문이 승인되었고 아직 취소되지 않았다면 주문 전체를 취소한다. 취소된 수량은 해당 메뉴의 재고에 즉시 돌아오며, 그 주문의 판매 대금 전액을 정산 대상에서 뺀다. 거절된 주문을 취소하거나 이미 취소된 주문을 다시 취소하는 요청은 아무 변화 없이 끝난다. 취소 요청 자체를 취소하는 입력은 주어지지 않는다. 모든 요청에는 종류와 관계없이 입력 순서대로 1부터 N까지 번호를 붙인다. 따라서 취소가 참조하는 번호는 주문만 따로 센 번호가 아니다. 메뉴 단가는 영업 중 바뀌지 않으며, 할인과 배달비 및 별도의 수수료는 없다. 마감 판매 대금은 승인된 뒤 끝까지 취소되지 않은 주문들의 단가와 수량의 곱을 모두 더한 값이다. 모든 요청을 처리한 뒤 이 금액과 메뉴별 남은 재고를 출력한다.

입력

첫째 줄에 메뉴 수 M과 요청 수 N이 공백으로 주어진다. M과 N은 정수이며 1 ≤ M, N ≤ 100,000이다.
다음 M개 줄의 i번째 줄에 메뉴 i의 단가 P_i와 초기 재고 S_i가 주어진다. 1 ≤ P_i ≤ 1,000,000,000, 0 ≤ S_i ≤ 1,000,000,000이다.
다음 N개 줄에 요청이 주어진다. 주문은 O x q 형태이며 1 ≤ x ≤ M, 1 ≤ q ≤ 1,000,000,000이다. 취소는 C t 형태이며 현재 요청 번호를 j라 할 때 1 ≤ t < j이고, t번째 요청은 반드시 주문이다.
모든 수치는 정수이다. 입력 전체의 크기는 줄바꿈과 공백을 포함하여 400,000바이트 이하이다.

출력

첫째 줄에 마감 판매 대금을 정수로 출력한다. 정산 대상 주문이 없으면 0을 출력한다. 둘째 줄에 메뉴 1부터 M까지의 남은 재고를 공백으로 구분하여 출력한다.

2 7
500 3
800 2
O 1 2
O 1 2
O 2 1
C 1
O 1 3
C 1
C 3

1500
0 2

1 4
1000000000 1000000000
O 1 1000000000
O 1 1
C 2
C 1

0
1000000000

1 1
1000000000 1000000000
O 1 1000000000

1000000000000000000
0

출처: Devin.KR 자체 제작