Change
Time limit2sMemory limit512 MB
Pay the exact amount from limited 5, 10, 20 and 50 cent coins with the fewest coins, breaking ties toward larger denominations.
Problem
Jack Sagert carries a pocket full of change made up of 5, 10, 20 and 50 cent coins. Whenever he pays for something he picks the coins so that he hands over as few of them as possible. He is convinced that carrying a lot of change everywhere is his destiny in life, so he parts with the smallest number of coins he can.
Nobody knows how he ended up this way. The story goes that his mother's gynaecologist dropped him on his head the day he was born.
You are given how many 5, 10, 20 and 50 cent coins sit in his pocket and the amount he has to pay. Work out how many coins of each denomination he hands over and the total number of coins he uses. That total must be as small as possible.
Jack gets no change back, so the amount has to be matched exactly. If something costs $2.35 and the coins in his pocket cannot add up to 235 cents, he cannot pay for it.
Input
The first line contains five integers separated by spaces. The first four are the number of 5, 10, 20 and 50 cent coins Jack has, in that order, and the fifth is the amount he has to pay, in cents. Each coin count is smaller than 1,000,000, and the amount is an integer that is at least 0 and smaller than 100,000,000.
Output
Print on one line, separated by spaces, how many 5, 10, 20 and 50 cent coins Jack hands over, followed by the total number of coins he uses. That total must be as small as possible.
If more than one selection reaches the amount with that minimum number of coins, print the one that uses the fewest 5 cent coins. If a tie remains, take the one with the fewest 10 cent coins, and after that the one with the fewest 20 cent coins.
If the coins in his pocket cannot make the amount exactly, print -1 and nothing else.