题意：

给出一个价格n和一些零钱的数量$c_1,c_5,c_{10},c_{20},c_{50},c_{100},c_{200},c_{500},c_{1000},c_{2000}$。求最多用多少零钱凑出这个n。

思路：

用最少的零钱凑会比用最多的零钱凑好考虑。

如果零钱是1,5,10,50,100,200,1000,2000的话，就可以从大到小直接贪心取，就是每个零钱都是后面一个的约数的时候就可以直接贪心取。但是题目这种情况就不能这么做了，比如20,20,20,50,50，要取110，如果用这种策略的话，是凑不到110的，实际上是可以20+20+20+50的，50要少取一张。所以搜索一下两种情况，取满和取满-1。

代码：

typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll val[10]={1,5,10,20,50,100,200,500,1000,2000};
ll num[10];
ll ans;
void dfs(int id,ll sum,ll cnt)//当前种类/钱数/张数
{
    if(sum==0)
    {
        //printf("cnt=%lld\n",cnt);
        ans=min(ans,cnt);
        return;
    }
    if(id==-1)return;
    ll temp=min(num[id],sum/val[id]);
    //printf("id=%d sum=%lld temp=%lld\n",id,sum,temp);
    dfs(id-1,sum-temp*val[id],cnt+temp);
    if(temp>0)dfs(id-1,sum-(temp-1)*val[id],cnt+temp-1);
}
int main()
{
    int t;
    ll sum;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&sum);
        ll tot=0;//总钱数
        ll cnt=0;//总张数
        for(int i=0;i<10;i++)
        {
            scanf("%lld",&num[i]);
            tot+=val[i]*num[i];
            cnt+=num[i];
        }
        sum=tot-sum;
        if(sum<0)
        {
            printf("-1\n");
            continue;
        }
        //printf("sum=%lld cnt=%lld\n",sum,cnt);
        ans=INF;
        dfs(9,sum,0);
        //printf("ans=%lld\n",ans);
        if(ans==INF)printf("-1\n");
        else printf("%lld\n",cnt-ans);
    }
    return 0;
}