생산 라인의 두 품목 출고

문제

공장의 백엔드 담당자는 생산 라인에서 올라오는 입고 기록과 출고 주문을 처리한다. 공장은 여러 종류의 부품을 만들며, 각 품목에는 고정된 판매 단가와 현재 재고가 있다. 생산된 부품이 창고에 들어오면 해당 품목의 재고가 증가한다. 출고 주문은 서로 다른 두 품목을 함께 요구하며, 주문 전체를 처리할 수 있을 때만 출고한다. 처리할 기록은 실제 발생한 순서대로 주어진다. 입고 기록에는 품목 번호와 입고 수량이 적혀 있다. 이 기록을 만나면 해당 품목의 재고에 입고 수량을 즉시 더한다. 입고에는 비용이나 매출이 발생하지 않으며, 다른 품목의 재고는 변하지 않는다. 출고 주문에는 첫 번째 품목 번호와 요구 수량, 두 번째 품목 번호와 요구 수량이 적혀 있다. 두 품목의 현재 재고가 각각의 요구 수량 이상이면 주문을 승인한다. 승인한 경우 두 품목의 재고에서 요구 수량을 각각 빼고, 각 품목의 판매 단가에 출고 수량을 곱한 금액의 합을 누적 매출에 더한다. 두 품목 중 하나라도 재고가 부족하면 주문 전체를 거절한다. 거절한 주문에서는 어느 품목의 재고도 줄어들지 않으며 매출도 발생하지 않는다. 재고가 충분한 품목만 먼저 출고하거나, 부족한 수량을 나중에 채워 주는 처리는 하지 않는다. 거절한 주문을 보관했다가 이후 입고 뒤에 다시 처리하지도 않는다. 같은 두 품목을 요구하는 주문이 반복되어도 각 주문은 그 시점의 재고로 별도로 판단한다. 모든 기록을 처리한 뒤 승인한 주문 수, 거절한 주문 수, 누적 매출을 구하라. 입고 기록은 승인 또는 거절 주문 수에 포함하지 않는다. 단가는 기록 처리 중 바뀌지 않으며 할인, 세금, 배송비는 없다.

입력

첫째 줄에 품목 수 M과 기록 수 N이 주어진다. 2 ≤ M ≤ 1,000, 1 ≤ N ≤ 18,000이다.
다음 M개 줄 중 i번째 줄에 품목 i의 초기 재고 S_i와 판매 단가 P_i가 주어진다. 0 ≤ S_i ≤ 1,000, 1 ≤ P_i ≤ 1,000이다.
다음 N개 줄에 기록이 하나씩 주어진다.
입고 기록은 1 x q 형식이다. 1 ≤ x ≤ M, 1 ≤ q ≤ 1,000이다.
출고 주문은 2 a u b v 형식이다. 1 ≤ a, b ≤ M, a ≠ b, 1 ≤ u, v ≤ 99이다.
입력의 모든 수는 정수이다.

출력

승인한 주문 수, 거절한 주문 수, 누적 매출을 한 줄에 공백으로 구분하여 출력한다. 주문이 없으면 세 값 모두 0이다. 누적 매출은 32비트 부호 있는 정수 범위를 넘을 수 있다.

3 6
4 10
2 7
0 30
2 1 3 2 2
2 1 2 3 1
1 3 2
2 1 1 3 2
1 2 5
2 2 3 1 1

2 2 114

2 4
2 8
0 5
2 1 2 2 1
1 2 1
2 1 2 2 1
2 1 1 2 1

1 2 21

출처: Devin.KR 자체 제작