Untitled

#include <iostream>
using namespace std;

int N; 
int packages;
int prices[35]; 
int p[35][35]; 
int a[35]; 
int needs; 
int bought[35]; 
int total;

void reset(){
	for(int i = 0; i < N+5; i++){
		prices[i] = 0;
		a[i] = 0;
		bought[i] = 0;
		for(int j = 0; j < N+5; j++){
			p[i][j] = 0;
		}
	}
} // Fix

int buy(int k){
	int cnt = 0;
	for(int j = 1; j <= N; j++){
		if(p[k][j] == 1 && a[j] == 1 && bought[j] == 0) {
			cnt++;
		}
	}

	return cnt;
}

int calPrice(int k){
	int sum = 0;
	for(int j = 1; j <= N; j++){
		if(p[k][j] == 1 && a[j] == 1) {
			sum += prices[j];
		}
	}

	return sum;
}

void mark(int k){
	for(int j = 1; j <= N; j++){
		if(p[k][j] == 1 && a[j] == 1) {
			bought[j]++;
		}
	}
}

void unmark(int k){
	for(int j = 1; j <= N; j++){
		if(p[k][j] == 1 && a[j] == 1) {
			bought[j]--;
		}
	}
}

void Try(int sum, int cnt, int t){
	if(sum > total) return;

	if(cnt == needs){ 
		if(sum < total) total = sum;
		return;
	}

	if(t == packages && cnt < needs){ 
		for(int k = 1; k <= N; k++){
			if(bought[k] == 0 && a[k] == 1){
				sum += prices[k];
				if(sum > total) return;
			}
		}
		if(sum < total) total = sum;
		return;
	}

	for(int i = t + 1; i <= packages; i++){
		int c = buy(i);
		if(c > 0 && p[i][N+1] < calPrice(i)){ 
			if(sum + p[i][N + 1] > total) return;
			mark(i);
			Try(sum + p[i][N + 1], cnt + c, i);
			unmark(i);
		}else {
			Try(sum, cnt, i);
		}
	}
	
}

int main(){
	freopen("input.txt", "r", stdin);
	int T; cin >> T;

	for(int tc = 1; tc <= T; tc++){
		cin >> N;
		reset();

		for(int i = 1; i <= N; i++){
			cin >> prices[i];
			total += prices[i];
		}

		cin >> packages;
		for(int i = 1; i <= packages; i++){
			int price, cnt;
			cin >> price >> cnt;
			for(int j = 1; j <= cnt; j++){
				int x; cin >> x;
				p[i][x] = 1;
			}
			p[i][N + 1] = price;
			p[i][N + 2] = cnt;
		}

		cin >> needs;
		for(int i = 1; i <= needs; i++){
			int x; cin >> x;
			a[x] = 1;
		}

		Try(0, 0, 0);

		cout << "#" << tc << " " << total << endl;
	}

	return 0;
}