Ticket vending machines reappear in the Moscow Metro. You are asked to write a program that will calculate what change and what bills and coins you need to give to the passenger.
Input
First, the cost of the ticket that the passenger wants to purchase is entered, then the total number of banknotes and coins that he put into the machine, and then the denominations of each of these banknotes and coins. The input data is written on one line and separated by spaces. It is known that the sum of all banknotes is greater than the cost of the ticket. In all test examples, the cost of the – a natural number not exceeding 1,000 rubles, the number of banknotes and coins is not more than 50, the denomination of each does not exceed 500 rubles. The total amount of money put into the machine by the buyer exceeds the cost of the ticket.
Imprint
The program must calculate which banknotes and coins can be given change, and output the denomination of each of these banknotes or coins in random order. The machine can dispense change in banknotes of 10, 50, 100 and 500 rubles, as well as coins of 1, 2 and 5 rubles. If there are several solutions, it is required to issue any one of them. If there are no solutions, you need to display the text:
Sorry! Our monetary system is not perfect!
Please choose another way to pay!
thank you!
Examples
| # |
Input |
Output |
| 1 |
100 1500 |
50 100 100 100 50 |