# Coins

Description

Mary, a friend of little John, is going to have a birthday party. John would like to give her a present, so he opened his money-box and found there some coins. In Tralaland they have coins of values **1, 2, 5, 10, 20, 50, 100, 200, 500** and **1000 TD** (Tralaland dollar). He decided to buy a very nice doll in a nearby shop. He wants to pay the exact price (without change) and he wants to use the smallest possible number of his coins.

You should find out the smallest possible number of his coins.

Input

The input file contains several cases,each case contain one line,There are 11 integer in this line **C _{1}**,

**C**, ...,

_{2}**C**and

_{10}**V**.where

**C**,

_{1}**C**, ...,

_{2}**C**corresponding to the numbers of JohnÂ´s coins of values

_{10}**1, 2, ...,1000 TD**followed by an integer

**V**representing the price of the doll.

"0 0 0 0 0 0 0 0 0 0 0" representing the end of input.

Output

Sample Input

1 2 3 4 5 6 7 8 9 1 1 1 0 0 0 0 0 0 0 0 0 123 1 2 3 4 5 6 7 8 9 1 123 0 0 0 0 0 0 0 0 0 0 0

Sample Output

1 -1 4

Source

Editor