사고 싶은 음료수 버튼을 원하는 만큼 누른 다음 확인 버튼을 누르면 한번에 가격을 알려주고, 그 가격만큼의 지폐를 투입하면 음료수가 한꺼번에 나오고 거스름돈이 잔돈으로 함께 나오는 자판기가 있다고 하자. 

자판기 확인을 눌렀을 때 선택한 음료수들의 총 가격을 알려주고, 최소 금액의 거스름돈을 받기 위한 투입 금액, 거스름돈 액수, 그리고 거스름돈 동전 개수가 최소가 되도록 하는 동전별 갯수를 출력하는 프로그램을 작성하시오. 사용 가능한 지폐는 50,000원권, 10,000원권, 5,000원권, 1,000원권의 4가지 종류이고 거스름돈은 500원, 100원, 50원, 10원짜리 동전으로만 나오는 것으로 가정한다.

첫 줄에 테스트 케이스의 수(T)가 들어온다. 그 후 음료수의 종류(M)와 고른 메뉴의 수(N), 메뉴표와 가격, 고른 메뉴들이 차례로 나온다. 메뉴들의 가격은 최소 10원 단위로 가정한다.

(1 <= T <= 10, 1 <= M <= 10, 1 <= N <= 30, 100 <= 가격 <= 100,000)

* 메뉴이름은 중복되지 않으며, 메뉴이름의 길이는 영어 20자 이하이다.

테스트케이스 별로 선택한 음료수들의 총 금액, 최소 투입 금액, 최소 투입 금액을 위한 최소의 지폐 갯수, 거스름돈 액수, 거스름돈 동전 갯수가 최소가 되도록 하는 동전 종류별 갯수를 한 줄씩 출력한다. 각 값들 사이에는 공백을 하나만 둔다.(자세한 출력 형식은 출력 예시를 참고하시오)