Untitled

package backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class upgradePC {
	static int n;
	static int price[];
	static int arr[][];
	static int buy[];
	static int total;
	static int min;
	static int check[];
	static int numbuy;
	static int ud;

	static boolean checkBuy() {
		for (int i = 0; i < numbuy; i++) {
			if (check[buy[i]] == 0) {
				return false;
			}
		}
		return true;
	}

	static int sumBuy() {
		int c = total;
		for (int i = 0; i < numbuy; i++) {
			if (check[buy[i]] == 0) {
				c += price[buy[i]];
			}
		}
		return c;
	}

	static void backtrack(int v) {
		if (total > min) {
			return;
		}
		if (v == ud ) {
			if (checkBuy()) {
				if (total < min) {
					min = total;
				}
			} else {
				if (sumBuy() < min) {
					min = sumBuy();
				}
			}

			return;
		}

		for (int i = 0; i < 2; i++) {
			if (i == 0) {
				total += arr[v][0];
				for (int j = 0; j < arr[v][1]; j++) {
					check[arr[v][j + 2]]++;
				}
				backtrack(v + 1);
				total -= arr[v][0];
				for (int j = 0; j < arr[v][1]; j++) {
					check[arr[v][j + 2]]--;
				}
			} else {
				backtrack(v + 1);
			}
		}

	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("Text"));
		Scanner scanner = new Scanner(System.in);
		int tc = scanner.nextInt();
		for (int Case = 1; Case <= tc; Case++) {
			n = scanner.nextInt();
			price = new int[n + 1];
			for (int i = 1; i <= n; i++) {
				price[i] = scanner.nextInt();
			}

			ud = scanner.nextInt();
			arr = new int[ud][n + 1];
			for (int i = 0; i < ud; i++) {
				arr[i][0] = scanner.nextInt();
				arr[i][1] = scanner.nextInt();
				for (int j = 0; j < arr[i][1]; j++) {
					arr[i][j + 2] = scanner.nextInt();
				}
			}
			numbuy = scanner.nextInt();
			buy = new int[numbuy];
			for (int i = 0; i < numbuy; i++) {
				buy[i] = scanner.nextInt();
			}
			check = new int[n+1];
			total = 0;`
			min = Integer.MAX_VALUE;
			backtrack(0);
			System.out.println("#"+ Case+" "+ min);
		}
	}
}