#2420 자판기 거스름돈

18  1 s   128 MB  

Description

사고 싶은 음료수 버튼을 원하는 만큼 누른 다음 확인 버튼을 누르면 한번에 가격을 알려주고,

그 가격만큼의 지폐를 투입하면 음료수가 한꺼번에 나오고 거스름돈이 잔돈으로 함께 나오는 자판기가 있다고 하자.

자판기 확인을 눌렀을 때 선택한 음료수들의 총 가격을 알려주고, 최소 금액의 거스름돈을 받기 위한 투입 금액, 거스름돈 액수, 거스름돈 동전 개수를 출력하는 프로그램을 작성하시오.

사용 가능한 지폐는 50,000원권, 10,000원권, 5,000원권, 1,000원권의 4가지 종류이고 거스름돈은 500원, 100원, 50원, 10원짜리 동전으로만 나오는 것으로 가정한다.

Input

첫 줄에 테스트 케이스의 수($T$)가 들어온다. 그 후 음료수의 종류($M$)와 고른 메뉴의 수($N$), 메뉴표와 가격($P$), 고른 메뉴들이 차례로 나온다.

메뉴들의 가격은 최소 $10$원 단위로 가정한다.

$(1 \leq T \leq 10, 1 \leq M \leq 10, 1 \leq N \leq 30, 100 \leq P \leq 100,000)$

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

Output

선택한 음료수들의 총 금액, 최소 투입 금액, 거스름돈 액수, 거스름돈 동전 개수를 한 줄씩 출력한다.

각 값들 사이에는 공백을 하나만 둔다.

Sample Input

Sample Output

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

Source

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