Problem Description
You are a rich person, and you think your wallet is too heavy and full now. So you want to give me some money by buying a lovely pusheen sticker which costs p dollars from me. To make your wallet lighter, you decide to pay exactly p dollars by as many coins and/or banknotes as possible.
For example, if p=17 and you have two $10 coins, four $5 coins, and eight $1 coins, you will pay it by two $5 coins and seven $1 coins. But this task is incredibly hard since you are too rich and the sticker is too expensive and pusheen is too lovely, please write a program to calculate the best solution.
Input
The first line contains an integer T indicating the total number of test cases. Each test case is a line with 11 integers p,c1,c5,c10,c20,c50,c100,c200,c500,c1000,c2000, specifying the price of the pusheen sticker, and the number of coins and banknotes in each denomination. The number ci means how many coins/banknotes in denominations of i dollars in your wallet.
1≤T≤20000
0≤p≤109
0≤ci≤100000
Output
For each test case, please output the maximum number of coins and/or banknotes he can pay for exactly p dollars in a line. If you cannot pay for exactly p dollars, please simply output '-1'.
Sample Input
3
17 8 4 2 0 0 0 0 0 0 0
100 99 0 0 0 0 0 0 0 0 0
2015 9 8 7 6 5 4 3 2 1 0
Sample Output
9
-1
36
https://www.cnblogs.com/blvt/p/7788062.html
多重背包问题，机试指南上有
直接用0-1背包比较麻烦，但也可行。
ci>p的币种不用
每个币种组合成它的1,2,4,8直到k-2^c+1，总和为k。每个币种的值和数量算起来，列成数组。
动态规划
p=0返回0，
否则dp[p+1]，开始dp[0]=0，其他-1。flag=1；
如果dp[p-ci]！=-1，就可以马上输出其+1值，置flag=0；
否则逆向扫描行，dp[i]=max｛dp[i-币值]（不是-1）+1，dp[i]｝
结束后flag=0，则输出dp[p]=-1
当然一直扫完再输出也可以。
而不做分组也可以，毕竟p才109.