题意：

有\(10\)种面值为\(1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000\)的纸币，现在你要选最多的数量凑成\(p\)块钱。

分析：

同样分析问题的反面：设总金额为\(sum\)，我们来求凑成\(sum-p\)所需要的最少的张数。那么剩下的就是凑成\(p\)的最多的张数。

如果没有\(50\)和\(500\)的面值的话，那么后一种面值都是前一种面值的倍数，显然贪心是可以的。

贪心的理由就是完全可以用大面值替换掉对应数量的小面值的钱，这样总钱数不变但张数变少了。

考虑到\(50\)和\(500\)的存在，就会出现用大面值凑不成但用小面值能凑成的情况。

所以可以枚举\(50\)和\(500\)分别用了奇数张还是偶数张，然后剩下的\(50\)和\(500\)两张两张地取。

或者看成面值为\(100\)和\(1000\)的对答案贡献为2的纸币。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

int n, a[10], b[10];

int val[] = { 1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000 };

int sum, tot, ans;

//用最少张数的钱去凑n块钱

int solve(int n) {

	int ans = 0;

	for(int i = 9; i >= 0; i--) {

		if(i == 4 || i == 7) {   //50和500两张两张地取

			int t = min(n / (val[i] * 2), b[i] / 2);

			ans += t * 2;

			n -= val[i] * 2 * t;

		}

		else {

			int t = min(n / val[i], b[i]);

			ans += t;

			n -= t * val[i];

		}

		if(n == 0) break;

	}

	if(n > 0) return INF;

	else return ans;

}

//#define DEBUG

int main()

{

	int T; scanf("%d", &T);

	while(T--) {

		scanf("%d", &n);

		sum = 0, tot = 0;

		for(int i = 0; i < 10; i++) {

			scanf("%d", a + i);

			tot += a[i];

			sum += val[i] * a[i];

		}

		if(sum < n) { printf("-1\n"); continue; }

		#ifdef DEBUG

		printf("sum = %d, tot = %d, cou = %d\n", sum, tot, sum - n);

		#endif

		n = sum - n;

		ans = INF;

		for(int i = 0; i < 2; i++)

			for(int j = 0; j < 2; j++) {  //枚举50和500分别取了奇数个还是偶数个

				memcpy(b, a, sizeof(a));

				int t = n;

				if(i) {

					if(b[4]) { t -= 50; b[4]--;}

					else continue;

				}

				if(j) {

					if(b[7]) { t -= 500; b[7]--; }

					else continue;

				}

				if(t >= 0) ans = min(ans, solve(t) + i + j);

			}

		if(ans == INF) printf("-1\n");

		else printf("%d\n", tot - ans);

	}

	return 0;

}