지원 도구 이용료 정산

문제

한 회사의 사내 IT 지원팀은 여러 부서가 사용하는 원격 지원 도구의 월 이용료를 정산한다. 백엔드 담당자는 신청 기록을 읽고 부서별 청구 금액을 만드는 기능을 구현해야 한다. 부서 번호는 1부터 M까지이며, 신청 기록 하나에는 부서 번호와 추가로 신청한 이용권 수가 적혀 있다. 같은 부서가 여러 번 신청할 수 있으므로, 기록 한 줄마다 요금을 계산해서 더하는 방식으로는 올바른 결과를 얻을 수 없다. 먼저 각 부서에 속한 모든 신청 기록의 이용권 수를 합한다. 한 부서의 합계가 Q개라면 할인 전 이용료는 이용권 한 개당 120원씩, 총 120×Q원이다. 할인율은 해당 부서의 이용권 합계를 기준으로 한 번만 정한다. Q가 10 미만이면 할인하지 않고, 10 이상 50 미만이면 10퍼센트, 50 이상이면 20퍼센트를 할인한다. 할인율이 정해지면 그 부서의 전체 이용료에 같은 할인율을 적용한다. 구간마다 다른 할인율을 나누어 적용하지 않는다. 할인 후 이용료에 정산 수수료 35원을 더한 금액을 공급 금액이라고 한다. 세금은 공급 금액의 10퍼센트이며, 계산 결과에 1원 미만의 부분이 있으면 올림하여 정수 원으로 만든다. 최종 청구 금액은 공급 금액과 세금의 합이다. 이용권 가격과 할인율의 조합상 할인 후 이용료는 항상 정수이므로, 할인 단계에서는 별도의 반올림을 하지 않는다. 신청 기록이 전혀 없는 부서에는 수수료와 세금을 포함하여 아무 금액도 청구하지 않는다. 다른 부서의 신청량은 해당 부서의 할인율에 영향을 주지 않는다. 모든 신청 기록은 취소되지 않은 유효한 기록이며, 중복된 내용의 줄도 각각 별개의 신청으로 합산한다. 입력 순서는 부서 번호 순서가 아닐 수 있다. 모든 기록을 처리한 뒤, 신청하지 않은 부서까지 포함하여 부서 번호가 작은 순서대로 최종 청구 금액을 출력하는 프로그램을 작성한다.

입력

첫째 줄에 신청 기록 수 N과 부서 수 M이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 20,000, 1 ≤ M ≤ 1,000이다.
다음 N개 줄에는 부서 번호 D와 신청한 이용권 수 K가 공백으로 구분되어 주어진다. 1 ≤ D ≤ M, 1 ≤ K ≤ 1,000이다. 입력의 모든 수는 정수이며, 모든 금액의 단위는 원이다.

출력

M개 줄을 출력한다. i번째 줄에는 i번 부서의 최종 청구 금액을 정수 하나로 출력한다. 신청 기록이 없는 부서는 0을 출력한다.

4 4
1 4
2 50
1 6
3 1

1227
5319
171
0

3 2
2 24
1 9
2 25

1227
5860

출처: Devin.KR 자체 제작