#1997 자판기의 거스름돈은 얼마인가?

65  1 s   128 MB  

Description

산학협력관에 있는 자판기는 너무 구식이어서 수십 개의 음료수를 사기 위해서는 너무 번거롭다. 천원 넣고 뽑고 넣고 뽑고 넣고 뽑고... 이게 수동판매기지 왜 자동판매기인가? 그래서 개선해 보고 싶은데 영 쉽지가 않다.

개선 방법은 사고 싶은 음료수 버튼을 마구마구 누르고 확인을 누르면 한번에 가격을 알려줘 그 가격만큼의 지폐를 투입하면 음료수가 우루루 나오고 거스름돈은 잔돈으로 나오도록 하는 것이다.

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

Input

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

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

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

Output

선택한 음료수들의 총 금액, 투입 금액, 최소 투입 지폐 개수, 거스름돈 액수, 거스름돈 동전 개수를 한 줄씩 출력한다. 각 값들 사이에는 공백을 하나만 둔다.

Sample Input

Sample Output

1
3 5
CanCoffee 500
CanCoke 700
Candy 200
Candy
CanCoke
Candy
CanCoffee
CanCoffee
2100 3000 3 900 5

Source

동의대학교 멀티미디공학과 우영운(2012년 6월 12일)