Untitled

#include <iostream>
using namespace std;

int N, M, K, skyMarket[21], combo[30][21], need[21], buy[21], minPrice;
bool hasNeed;

void select(int k) {
	hasNeed = false;
	for (int i = 2; i < combo[k][1] + 2; i++) {
		if (buy[combo[k][i]] < 1) hasNeed = true;
		buy[combo[k][i]]++;
	}
}

void deselect(int k) {
	for (int i = 2; i < combo[k][1] + 2; i++) {
		buy[combo[k][i]]--;
	}
}

bool check() {
	for (int i = 0; i < K; i++) {
		if (buy[need[i]] == 0) return false;
	}
	return true;
}

void backtrack(int k, int sum) {
	if (sum >= minPrice) return;
	if (check()) {		
		if (sum < minPrice) minPrice = sum;
		return;
	}
	if (!hasNeed) {
		hasNeed = true;
		return;
	}
	if (k == M) {
		int price = sum;
		for (int i = 0; i < K; i++) {
			if (buy[need[i]] == 0) {
				price += skyMarket[need[i]];
			}
		}
		if (price < minPrice) minPrice = price;
		return;
	}

	for (int i = 0; i < 2; i++) {
		if (i == 0) {
			backtrack(k + 1, sum);
		} else {
			select(k);
			backtrack(k + 1, sum + combo[k][0]);
			deselect(k);
		}
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		cin >> N;
		for (int i = 1; i <= N; i++) {
			cin >> skyMarket[i];
			buy[i] = 0;
		}
		cin >> M;
		for (int i = 0; i < M; i++) {
			cin >> combo[i][0] >> combo[i][1];
			for (int j = 2; j < 2 + combo[i][1]; j++) {
				cin >> combo[i][j];
			}
		}
		cin >> K;
		minPrice = 0;
		for (int i = 0; i < K; i++) {
			cin >> need[i];
			minPrice += skyMarket[need[i]];
		}
		hasNeed = true;
		backtrack(0, 0);
		cout << "#" << tc << " " << minPrice <<endl;
	}
	return 0;
}