Making Change

Given an amount of money and an almost unlimited number of coins (we ignore notes for this problem), an amount can be made up in many ways. A more interesting problem arises when goods are bought and paid for, with the possibility that change must be given back. Because most wallets hold only a finite number of coins, we are constrained in how we can make up the amount we pay---assuming we can make it up at all, but that is another story.

Our task is to minimise the total number of coins that change hands in such a transaction, assuming the shopkeeper has an adequate supply of every coin. The set of coins available is 5c, 10c, 20c, 50c, $1 and $2.

For example, suppose we must pay 55c and we do not hold a 50c coin. We could pay with 2 × 20c + 10c + 5c, a total of 4 coins. If instead we tender $1, we receive 45c in change, which also involves 4 coins. But if we tender $1.05 ($1 + 5c), we get 50c in change, and only 3 coins change hands in total.

Write a program that reads the coins available to you and the amount of the purchase, and determines the minimum number of coins that change hands.

The input consists of a series of lines, each describing a different situation. Each line contains 6 integers giving the number of coins available to you, in the order 5c, 10c, 20c, 50c, $1, $2, followed by a real number giving the value of the transaction, which is always less than $5.00. The input is terminated by a line of six zeroes (0 0 0 0 0 0). The coins you hold are always sufficient to pay the amount, and the amount is always achievable (it is always a multiple of 5c).

For each situation in the input, output one line containing the minimum number of coins that change hands, right-justified in a field 3 characters wide.