BNKQ

아프가니스탄의 Xyz 은행이 고객 때문에 골치를 썩이고 있다. 매달 말 정부 직원들의 급여가 계좌에 입금되면, 너무 많은 사람들이 돈을 인출하러 몰려든다. 은행은 창구 대기열을 관리하는 데 어려움을 겪고 있다. 고객들이 대기열에서 기다리는 시간을 줄이고 싶어 한다. 프로그램을 작성해 은행의 문제를 해결해 주자.

참고:

• 모든 창구는 같은 속도로 일한다.
• 고객 도착 사이의 시간 간격 외에는 지연이 없다.

첫 줄에는 테스트 케이스의 수 (T)가 주어진다: 0 < T < 100

• 다음 줄에는 현재 테스트 케이스의 창구 수 (C)와 고객 수 (N)가 공백으로 구분되어 주어진다: 0 < C < 10, 0 < N < 1000
• 그다음 N개의 줄에는 현재 고객이 이전 고객보다 몇 분 후에 은행에 도착하는지를 나타내는 수 (D)와 그 고객을 처리하는 데 걸릴 대략적인 분 수 (W)가 공백으로 구분되어 주어진다: 0 <= D < 30, 0 < W < 20

각 테스트 케이스마다 모든 고객을 처리하는 데 걸리는 대략적인 분 수를 출력한다.

테스트 케이스가 하나뿐이고, 창구가 2개, 고객이 5명이다. 각 고객은 자신의 요청을 처리하는 데 걸릴 시간을 대략적으로 추정한다. 모든 고객을 창구에 배치하면 다음과 같은 순서가 된다:

• [min1] => 1,2,3 도착

  • 1 => 1번 창구
  • 2 => 2번 창구
  • 3 => 1번 창구에서 1분 대기

• [min3] => 4 도착 (3보다 2분 후)

  • 4 => 2번 창구

• [min4] => 5 도착 (4보다 1분 후)

  • 5 => 1번 창구에서 1분 대기

고객이 도착할 때마다 가장 짧은 대기열에 배치된다. 모든 고객을 처리하는 데 9분이 걸린다 (첫 고객이 도착한 순간부터 마지막 고객이 처리될 때까지).