1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <cmath>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long           LL ;
15 typedef unsigned long long ULL ;
16 const int    maxn = 1e5 + 10   ;
17 const int    inf  = 0x3f3f3f3f ;
18 const int    npos = -1         ;
19 const int    mod  = 1e9 + 7    ;
20 const int    mxx  = 100 + 5    ;
21 const double eps  = 1e-6       ;
22 const double PI   = acos(-1.0) ;
23 
24 int c[11]={0,1,5,10,20,50,100,200,500,1000,2000};
25 int a[20], b[20], T, ans, tot;
26 LL p, sum;
27 int main(){
28     // freopen("in.txt","r",stdin);
29     // freopen("out.txt","w",stdout);
30     while(~scanf("%d",&T)){
31         while(T--){
32             sum=0;
33             tot=0;
34             ans=inf;
35             scanf("%lld",&p);
36             for(int i=1;i<11;i++){
37                 scanf("%d",&a[i]);
38                 tot+=a[i];
39                 sum+=a[i]*c[i];
40             }
41             if(sum<p){
42                 printf("-1\n");
43                 continue;
44             }
45             p=sum-p;
46             memcpy(b,a,sizeof(a));
47             for(int i=0;i<2;i++)
48                 for(int j=0;j<2;j++)
49                     if(i<=a[5] && j<=a[8]){
50                         b[5]=a[5]-i;
51                         b[8]=a[8]-j;
52                         LL t=p-i*c[5]-j*c[8];
53                         int cnt=i+j;
54                         for(int k=10;k>0&&t>0;k--){
55                             int del=min(b[k],(int)t/c[k]);
56                             if((k==5||k==8)&&(del&1))
57                                 del--;
58                             t-=del*c[k];
59                             cnt+=del;
60                         }
61                         if(t==0)
62                             ans=min(ans,cnt);
63                     }
64             if(ans==inf)
65                 ans=-1;
66             else
67                 ans=tot-ans;
68             printf("%d\n",ans);
69         }
70     }
71     return 0;
72 }