Untitled

#include <iostream>
using namespace std;

int N;
int likien[21];
int combo[31][21];
int cnt[21];
int M;
int nesary[21] = { 0 };
int arr[21];
int giatri[21] = { 0 };
int sl;

void reset(int ar[21])
{
	for (int i = 0; i < 21; i++)
	{
		ar[i] = 0;
	}
}

int sum()
{
	int sm = 0;
	for (int i = 1; i <= N; i++)
	{
		sm = sm + giatri[i];
	}
	return sm;
}


bool check()
{
	for (int i = 1; i <= N; i++)
	{
		if (nesary[i] >= 1)
		{
			return false;
		}
	}
	return true;
}

void linh_kien(int& min, int k)
{
	if (check() == true)
	{
		int sm = sum();
		if (min > sm)
		{
			min = sm;
		}
		return;
	}
	if (k >= sl + 1)
	{
		return;
	}
	int t = sum();
	if (t > min)
	{
		return;
	}
	for (int i1 = 0; i1 <= 1; i1++)
	{
		if (i1 == 0)
		{
			// khoong mua gi ca
			linh_kien(min, k + 1);
		}
		else
		{
			// mua online combo
			// neu thieu mua cho troi
			for (int i = 1; i <= M; i++)
			{
				int ar[21] = { 0 };
				int k1 = 0;
				for (int j = 1; j <= N; j++)
				{
					if (nesary[j] == 1 && combo[i][j] != 0)
					{
						ar[k1] = j;
						k1++;
					}
				}
				if (k1 > 0)
				{
					giatri[ar[k1 - 1]] = combo[i][ar[k1 - 1]];
					for (int t = 0; t < k1; t++)
					{
						nesary[ar[t]] = 0;
					}
					linh_kien(min, k + k1);
					giatri[ar[k1 - 1]] = 0;
					for (int t = 0; t < k1; t++)
					{
						nesary[ar[t]] = 1;
					}
				}
			}
		}
	}
	// kiem tra neu thieu thi mua them cho troi
	for (int i = 0; i <= N; i++)
	{
		if (nesary[i] == 1)
		{
			nesary[i] = 0;
			giatri[i] = likien[i];
			linh_kien(min, k+ 1);
			nesary[i] = 1;
			giatri[i] = 0;

		}
	}

}

int main()
{
	int testcase;
	cin >> testcase;
	for (int tc = 1; tc <= testcase; tc++)
	{
		reset(nesary);
		reset(cnt);
		reset(likien);
		reset(giatri);
		cin >> N;
		for (int i = 0; i < 31; i++)
		{
			for (int j = 0; j < 21; j++)
			{
				combo[i][j] = 0;
			}
		}
		for (int i = 1; i <= N; i++)
		{
			cin >> likien[i];
		}
		cin >> M;
		for (int i = 1; i <= M; i++)
		{
			int gtri;
			cin >> gtri >> cnt[i];
			for (int j = 1; j <= cnt[i]; j++)
			{
				int x;
				cin >> x;
				combo[i][x] = gtri;
			}
		}
		cin >> sl;
		for (int i = 1; i <= sl; i++)
		{
			int x;
			cin >> x;
			nesary[x] = 1;
		}
		// mua o cho troi truoc roi mua online
		int min = 1000;
		linh_kien(min, 1);
		cout << "#" << tc << " " << min << endl;
	}
}