Coins

1000ms    65536K
157    35
Easier

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 C1, C2, ...,C10 and V .where C1, C2, ...,C10 corresponding to the numbers of John´s coins of values 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

Print the smallest possible number of his coins.If this impossible print -1.

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

on 2009-12-24 20:54:56


North University of China

OnlineJudge

NUC

NOJ

OJ

ACM/ICPC