nang cap may tinh

package practise;

import java.util.Scanner;

public class nang_cap_may_tinh {
	
	static int n_equip, n_sale, n_use, ans;
	static int[] price_CT, price_sale, usage, bought;
	static boolean[] visit;
	static int[][] sales;
	
//	private static boolean check() {
//		for(int i = 0; i < n_use; i++) {
//			if(bought[i] == -1) return false;
//		}
//		return true;
//	}
	
	private static void backtrack(int sale, int cnt, int price) {
		if(cnt == n_use) {
			ans = ans > price ? price : ans;
			return;
		}
		
		if(sale == n_sale) {
			int tmp = 0;
			for(int i = 0; i < n_use; i++) {
				if(bought[i] == -1) {
					tmp += price_CT[usage[i]];
				}
			}
			ans = ans > tmp + price ? tmp + price : ans;
			return;
		}
		
		visit[sale] = true;
		int sum = 0, tmp = 0;
		for(int i = 0; i < n_use; i++) {
			if(bought[i] == -1 && sales[sale][usage[i]] != 0) {
				bought[i] = cnt;
				tmp++;
				sum += price_CT[usage[i]];
			}
		}
		
		if(tmp != 0) {
			if(sum > price_sale[sale]) {
				backtrack(sale + 1, cnt + tmp, price + price_sale[sale]);
			}
			else backtrack(sale + 1, cnt + tmp, price + sum);
			
			for(int i = 0; i < n_use; i++) {
				if(bought[i] == cnt) bought[i] = -1;
			}
			
		}
		else backtrack(sale + 1, cnt, price);
		
		visit[sale] = false;
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for(int tc = 1; tc <= testcase; tc++) {
			n_equip = sc.nextInt() + 1;
			price_CT = new int[n_equip];
			
			for(int i = 1; i < n_equip; i++) {
				price_CT[i] = sc.nextInt();
			}
			
			n_sale = sc.nextInt() + 1;
			sales = new int[n_sale][n_equip];
			price_sale = new int[n_sale];
			int equip, price, tmp;
			for(int i = 1; i < n_sale; i++) {
				price = sc.nextInt();
				price_sale[i] = price;
				equip = sc.nextInt();
				for(int j = 0; j < equip; j++) {
					tmp = sc.nextInt();
					sales[i][tmp] = price;
				}
			}
			
			
			n_use = sc.nextInt();
			usage = new int[n_use];
			bought = new int[n_use];
			for(int i = 0; i < n_use; i++) {
				usage[i] = sc.nextInt();
				bought[i] = -1;
				
			}
			
			visit = new boolean[n_sale];
			ans = Integer.MAX_VALUE;
			
			if(n_sale == 1) {
				ans = 0;
				for(int i = 0; i < n_use; i++) {
					ans += price_CT[usage[i]];
				}
			}
			else {
				for(int i = 1; i < n_sale; i++) {
					backtrack(i, 0, 0);
				}
			}
//			backtrack(1, 0, 0);
			System.out.println("#" + tc + " " + ans);
//			return;
		}
	}
}