SHOP

면접 대비

시간 제한2초메모리 제한512 MB

요약

거슬러 줄 금액과 각 화폐 단위의 보유 수량이 주어질 때, 큰 단위부터 사용해 금액을 정확히 맞추는 방법을 찾는다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬, 구현, 수학
정답자: 아직 제출이 없습니다

문제

Ahmad는 시장에서 일하는 상인이다. 손님이 쇼핑한 값을 지불하면 Ahmad는 거스름돈을 돌려줘야 한다. Ahmad는 가능하면 항상 가장 큰 지폐로 지불하려고 한다. Ahmad를 도와줄 프로그램을 작성하자.

입력

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

각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 Ahmad가 손님에게 돌려줘야 하는 금액 $M$ 이 주어진다. ( $1 \le M \le 1000000$ ) 둘째 줄에는 $m_1:a_1, \dots, m_i:a_i, \dots, m_n:a_n$ 형식으로 지폐 정보가 주어진다. $m_i$ 는 지폐의 액면가이고 $a_i$ 는 그 액면가의 지폐를 가진 개수이다. ( $1 \le m \le 1000000$ )

출력

Ahmad가 손님에게 돌려줘야 하는 지폐를 액면가 내림차순으로 출력한다.

예제1

예제 1

입력

3
235
5:10,10:6,20:4,50:3
370
10:4,5:20,40:4,70:3,100:2,50:5
172
10:4,5:20,40:4,70:3,100:2,50:5

예상 출력

Customer1:
50 3
20 4
5 1
Customer2:
100 2
70 2
10 3
Customer3:
Impossible