Description
There is a beverage vending machine in Sudeok Hall at Dong-eui University. This machine is outdated, making it very cumbersome to purchase multiple drinks. This is because you have to insert money, take out one, insert money again, take out another, and so on to make multiple purchases. Therefore, Bilal wants to create a new vending machine program to make it more convenient.
The new vending machine program is structured so that when the user presses the button for the 'type' of drink they want to buy, enters the desired 'quantity', and presses 'confirm', then presses the button for another 'type' of drink, enters the desired 'quantity' again, and presses 'confirm', and so on, until finally pressing the 'complete' button, it displays the total price, and if the user inserts that amount of money, all the drinks are dispensed.
Write a program that, when the 'complete' button is pressed, displays the total price of the selected drinks, the amount inserted to receive the minimum amount of change, and the number of each coin type that minimizes the change amount. It is assumed that there are four types of usable banknotes: 50,000 won, 10,000 won, 5,000 won, and 1,000 won, and that change is given only in three types of coins: 500 won, 100 won, and 50 won.
Input
The number of test cases is entered on the first line.
The next line contains the types of beverages (n_menu), and the names of the beverages are unique. (1 <= n_menu <= 10)
Starting from the next line, the types of beverages and their prices (price) are entered on n_menu lines. (500 <= price <= 5,000) All beverage prices are multiples of 50.
The next line contains the number of beverage types to be purchased (drink_num). (1 <= drink_num <= n_menu <= 10)
Starting from the next line, the selected beverage types and the quantity to be purchased (buy_num) are entered on drink_num lines. (1 <= buy_num <= 5)
Output
For each test case, output the total amount of the selected beverages, the minimum insertion amount, the minimum number of bills required for the minimum insertion amount, the amount of change, and the quantity of each coin type that minimizes the change, on a separate line. Leave only a single space between each value. (Refer to the sample output for the detailed output format.)
1
3
CanCoffee 650
CanCoke 500
CanOranC 700
2
CanCoffee 3
CanOranC 5
Total:5450 Money:6000 Bills:2 Change:550(500:1 100:0 50:1)