카페 마감 묶음 할인

문제

카페의 백엔드 담당자는 하루 동안 접수한 음료 주문을 모아 마감 정산서를 만든다. 이 카페는 같은 메뉴를 여러 잔 주문하면 일부 잔을 무료로 제공하는 행사를 운영한다. 메뉴마다 한 잔의 가격과 행사 기준 잔 수가 정해져 있으며, 정산할 때는 주문 기록별로 할인하지 않고 하루 전체의 메뉴별 주문 수량을 합쳐 계산한다. 메뉴 i의 한 잔 가격을 P_i, 행사 기준 잔 수를 K_i라고 하자. 하루 동안 메뉴 i가 모두 Q_i잔 주문되었다면, 이 중 Q_i를 K_i로 나눈 몫만큼의 잔을 무료로 제공한다. 나머지 잔에는 모두 한 잔 가격을 적용한다. 예를 들어 행사 기준이 4잔인 메뉴가 하루 동안 9잔 주문되었다면 2잔은 무료이고 7잔의 가격을 받는다. 무료로 제공하는 잔도 주문된 전체 수량에 포함되며, 무료 잔을 제외한 수량으로 행사를 다시 계산하지 않는다. 각 주문 기록에는 메뉴 번호 하나와 주문 수량이 적혀 있다. 같은 메뉴의 주문이 여러 기록에 나뉘어 있을 수 있으므로, 서로 떨어져 있는 기록도 모두 합쳐야 한다. 반면 서로 다른 메뉴의 수량은 행사 기준이나 가격이 같더라도 합치지 않는다. 어떤 메뉴도 주문하지 않은 경우 그 메뉴의 유료 수량과 무료 수량은 모두 0이다. 모든 주문은 정상적으로 제공되었으며 취소나 환불은 없다. 주문 기록의 순서는 정산 결과에 영향을 주지 않고, 다음 날로 넘기는 잔 수나 이전 날에서 가져오는 잔 수도 없다. 메뉴별 가격과 행사 기준은 하루 동안 바뀌지 않으며, 세금이나 별도의 추가 요금은 계산하지 않는다. 전체 주문 기록을 바탕으로 손님들에게 받아야 할 최종 금액과 무료로 제공한 전체 잔 수를 구하라. 최종 금액은 각 메뉴의 유료 잔 수에 해당 메뉴의 가격을 곱한 뒤 모두 더한 값이다.

입력

첫째 줄에 메뉴 수 M과 주문 기록 수 N이 주어진다. 1 ≤ M ≤ 1,000, 1 ≤ N ≤ 30,000이다.
다음 M개 줄 중 i번째 줄에 메뉴 i의 한 잔 가격 P_i와 행사 기준 잔 수 K_i가 주어진다. 1 ≤ P_i ≤ 100,000, 2 ≤ K_i ≤ 10이다.
다음 N개 줄에 메뉴 번호 x와 주문 수량 q가 주어진다. 1 ≤ x ≤ M, 1 ≤ q ≤ 10이다.
입력의 모든 수는 정수이다.

출력

최종 금액과 무료로 제공한 전체 잔 수를 한 줄에 공백으로 구분하여 출력한다. 무료로 제공한 잔이 없으면 두 번째 값은 0이다. 최종 금액은 32비트 부호 있는 정수 범위를 넘을 수 있다.

3 5
4000 3
2500 4
5000 2
1 2
2 3
1 3
3 1
2 2

31000 2

2 2
100000 10
700 2
1 1
2 1

100700 0

1 2
1200 2
1 3
1 3

3600 3

출처: Devin.KR 자체 제작