Untitled

#include<iostream>

using namespace std;
int N;					// so linh kien chinh
int RetailPrices[25];	// gia cho Troi
int M;					// so goi uu dai
int ComboPrice[35];		// gia cua combo
int ComboSize[35];		// so luong item cua combo
int ComboList[35][25];	// cac goi uu dai
int NumNeed;			// so linh kien cam mua
int NeedList[25];		// cac linh kien can mua
int visitItems[25];		// item da mua
int ans;

int buyCombo(int c){
	int cnt = 0;	
	for (int i = 1; i <= ComboSize[c]; i++){
		if (NeedList[i] == 1 && ComboList[c][i] == 1){
			cnt++;
		}
	}
	return cnt;
}

void Try(int gia, int damua, int comboI){
	if (gia > ans) return;
	if (damua == NumNeed) {
		if (gia < ans) ans = gia;
		return;
	}
	if (comboI == M+1 && damua < NumNeed){
		for (int i = 1; i <= N; i++){
			if (NeedList[i] == 1 && visitItems[i] == 0){
				gia += RetailPrices[i];
			}
		}
		if (gia < ans) ans = gia;
		return;
	}

	int cntComboI = buyCombo(comboI);
	if (cntComboI > 0){
		// 1. mua combo
		for (int i = 1; i <= N; i++){
			if (NeedList[i] == 1 && ComboList[comboI][i] == 1){
				visitItems[i]++;
			}
		}
		Try(gia+ComboPrice[comboI],damua+cntComboI,comboI+1);
		// 2. khong mua combo
		for (int i = 1; i <= N; i++){
			if (NeedList[i] == 1 && ComboList[comboI][i] == 1 && visitItems[i]!=0){
				visitItems[i]--;
			}
		}
		Try(gia, damua, comboI+1);
	}else{
		Try(gia, damua, comboI+1);
	}
}

void reset(){
	ans = 0;
	for (int i = 1; i <= 25; i++){
		RetailPrices[i] = 0; 
		NeedList[i] = 0;
		visitItems[i] = 0;
	}
	for (int i = 1; i <= 35; i++){
		ComboPrice[i] = 0;
		ComboSize[i] = 0;
		for (int j = 1; j <= 25; j++){
			ComboList[i][j] = 0;
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	int TC; cin >> TC;
	for (int tc = 1; tc <= TC; tc++){
		reset();
		cin >> N;
		for (int i = 1; i <= N; i++) {
			// gia tung item mua cho Troi
			cin >> RetailPrices[i];
		}

		cin >> M;
		for (int i = 1; i <= M; i++){
			// so item cua combo
			cin >> ComboPrice[i] >> ComboSize[i];
			for (int j = 1; j <= ComboSize[i]; j++) {
				// item co trong combo = 1
				int itemI; cin >> itemI;
				ComboList[i][itemI] = 1;
			}
		}

		for (int i = 1; i <= M; i++){
			for (int j = 1; j <= N; j++) {
				cout << ComboList[i][j] << " ";
			}
			cout << endl;
		}

		cin >> NumNeed;
		for (int i = 1; i <= NumNeed; i++){
			int need; cin >> need;
			// item can mua = 1
			NeedList[need] = 1;
			ans += RetailPrices[need];
		}

		Try(0,0,1);

		cout << "#" << tc << " " << ans << endl;
	}
	return 0;
}