급식 추가 주문 정산

문제

학교 급식실은 점심 배식을 마친 뒤 남은 메뉴를 추가 주문으로 판매한다. 백엔드 담당자는 메뉴별 재고와 주문 목록을 받아, 정해진 우선순위에 따라 주문을 처리하고 정산 결과를 계산해야 한다. 메뉴에는 1번부터 M번까지 번호가 붙어 있으며, 각 메뉴의 시작 재고와 한 개당 판매 가격이 주어진다. 주문에는 1번부터 N번까지 입력 순서대로 번호가 붙는다. 각 주문은 메뉴 번호, 주문 수량, 우선순위 값으로 이루어진다. 우선순위 값이 작은 주문을 먼저 처리한다. 우선순위 값이 같으면 주문 번호가 작은 주문을 먼저 처리한다. 주문 번호는 입력 순서로만 정하며, 메뉴 번호나 주문 수량은 동점 처리에 영향을 주지 않는다. 주문을 처리하는 순간 해당 메뉴의 남은 재고가 주문 수량 이상이면 주문 전체를 승인한다. 이때 주문 수량만큼 재고를 줄이고, 주문 수량에 해당 메뉴의 한 개당 판매 가격을 곱한 금액을 매출에 더한다. 남은 재고가 주문 수량보다 적으면 주문 전체를 거절한다. 일부 수량만 판매하거나, 거절한 주문을 나중에 다시 처리하는 일은 없다. 같은 메뉴를 주문한 기록이 여러 개 있어도 각각 별개의 주문으로 처리한다. 주문을 처리하는 동안 메뉴 가격은 바뀌지 않으며, 재고가 추가되거나 승인된 주문이 취소되는 일도 없다. 승인 주문 수는 판매한 음식 개수가 아니라 승인된 주문 기록의 개수다. 모든 주문을 처리한 뒤 승인 주문 수, 총매출, 모든 메뉴의 남은 재고를 합한 값을 구한다. 승인된 주문이 없으면 승인 주문 수와 총매출은 모두 0이다. 한 번도 주문되지 않은 메뉴의 재고도 마지막 재고 합계에 포함한다.

입력

첫째 줄에 정수 M과 N이 주어진다. 1 ≤ M ≤ 1,000, 1 ≤ N ≤ 10,000이다.
다음 M개 줄의 i번째 줄에 i번 메뉴의 시작 재고 S_i와 한 개당 가격 C_i가 주어진다. 0 ≤ S_i ≤ 100,000, 1 ≤ C_i ≤ 100,000이며 모두 정수다.
다음 N개 줄에 입력 순서대로 각 주문의 메뉴 번호 A, 수량 Q, 우선순위 P가 주어진다. 1 ≤ A ≤ M, 1 ≤ Q ≤ 100,000, 1 ≤ P ≤ 100,000이며 모두 정수다.

출력

승인 주문 수, 총매출, 모든 메뉴의 남은 재고 합계를 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 모든 값은 정수로 출력한다.

2 5
7 1000
4 1500
1 5 2
1 3 1
2 4 2
1 4 2
2 1 3

3 13000 0

2 3
0 800
2 1200
1 1 1
2 3 1
2 5 2

0 0 2

1 3
5 700
1 4 3
1 2 3
1 1 3

2 3500 0

출처: Devin.KR 자체 제작