수족관 기념품의 세 번째 주문

문제

수족관 기념품점의 백엔드 담당자는 하루 동안 들어온 주문을 순서대로 처리하는 정산 기능을 만든다. 상품에는 1부터 K까지의 번호가 붙어 있으며, 상품마다 개점 시점의 재고 수량과 한 개의 가격이 정해져 있다. 하루 동안 추가 입고나 가격 변경은 없고, 주문은 입력에 주어진 순서 그대로 처리한다. 각 주문은 한 종류의 상품과 주문 수량으로 이루어진다. 같은 내용의 주문이 여러 번 들어와도 각각 별개의 주문이다. 주문을 처리할 때 해당 상품의 현재 재고가 주문 수량 이상이면 주문 전체를 성공 처리한다. 성공한 주문의 수량만큼 재고를 즉시 줄이고 결제 금액을 매출에 더한다. 현재 재고가 부족하면 주문 전체를 거절한다. 일부 수량만 판매하는 일은 없으며, 거절한 주문은 재고와 매출에 아무 영향도 주지 않는다. 뒤에 들어온 작은 주문은 앞선 주문이 거절되었더라도 남은 재고로 성공할 수 있다. 기념품점은 상품별로 세 번째 성공 주문마다 한 개를 무료로 주는 행사를 진행한다. 각 상품의 성공 주문 횟수는 하루 시작 시 0이다. 주문이 성공하면 해당 상품의 성공 횟수를 먼저 1 늘린다. 늘어난 횟수가 3의 배수이면 이번 주문 수량 중 정확히 한 개의 가격을 받지 않는다. 그 밖의 성공 주문은 모든 수량의 가격을 받는다. 따라서 수량이 q이고 가격이 p라면 행사 주문의 결제 금액은 (q-1)×p이며, 일반 주문의 결제 금액은 q×p다. 무료로 주는 한 개도 실제로 출고하므로 재고는 언제나 주문 수량 전체만큼 줄어든다. 수량이 1인 행사 주문은 결제 금액이 0이지만 성공 주문으로 센다. 거절한 주문은 행사 횟수를 늘리지 않으며 다른 상품의 성공 횟수에도 영향을 주지 않는다. 모든 주문을 처리한 뒤 총매출, 성공 주문 수, 거절 주문 수, 모든 상품의 남은 재고 수량의 합을 출력한다. 성공 주문이 없으면 총매출과 성공 주문 수는 모두 0이다.

입력

첫째 줄에 상품 수 K와 주문 수 N이 주어진다. K와 N은 정수이며 1 ≤ K ≤ 100, 1 ≤ N ≤ 20,000이다.
다음 K개 줄에 상품 번호 1번부터 K번까지의 초기 재고 s와 개당 가격 p가 주어진다. s와 p는 정수이며 0 ≤ s ≤ 1,000,000, 1 ≤ p ≤ 1,000,000이다.
다음 N개 줄에 주문 상품 번호 x와 주문 수량 q가 주어진다. x와 q는 정수이며 1 ≤ x ≤ K, 1 ≤ q ≤ 100이다.

출력

모든 주문을 처리한 총매출, 성공 주문 수, 거절 주문 수, 모든 상품의 남은 재고 수량의 합을 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 각 값은 정수로 출력한다.

2 6
5 100
3 200
1 2
1 2
1 2
1 1
2 3
2 1

1000 4 2 0

1 2
0 999
1 1
1 1

0 0 2 0

1 4
4 75
1 1
1 1
1 1
1 1

225 4 0 0

출처: Devin.KR 자체 제작