Untitled

import java.util.Scanner;

public class Main {
    // Biến toàn cục để lưu thông tin về số lượng thiết bị, gói ưu đãi và thiết bị cần thiết
    static int N, M, L;
    static int[] prices; // Mảng lưu giá các thiết bị ở chợ Trời
    static int[][] offers; // Mảng lưu các gói ưu đãi
    static int[] needed; // Mảng lưu số lượng thiết bị cần thiết
    static int minCost; // Biến lưu tổng chi phí nhỏ nhất tìm được

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // Đọc số lượng test case

        for (int t = 0; t < T; t++) {
            // Đọc số lượng thiết bị và giá của chúng ở chợ Trời
            N = sc.nextInt();
            prices = new int[N];
            for (int i = 0; i < N; i++) {
                prices[i] = sc.nextInt();
            }

            // Đọc số lượng gói ưu đãi và thông tin của chúng
            M = sc.nextInt();
            offers = new int[M][];
            for (int i = 0; i < M; i++) {
                int P = sc.nextInt(); // Giá của gói ưu đãi
                int K = sc.nextInt(); // Số lượng thiết bị trong gói
                offers[i] = new int[K + 1];
                offers[i][0] = P; // Giá của gói ưu đãi
                for (int j = 1; j <= K; j++) {
                    offers[i][j] = sc.nextInt() - 1; // Thiết bị (zero-based index)
                }
            }

            // Đọc thông tin về các thiết bị mà anh Kim cần mua
            L = sc.nextInt();
            needed = new int[N];
            for (int i = 0; i < L; i++) {
                needed[sc.nextInt() - 1]++; // Cập nhật số lượng thiết bị cần thiết
            }

            // Khởi tạo minCost với giá trị lớn nhất để tìm giá trị nhỏ nhất
            minCost = Integer.MAX_VALUE;
            // Gọi hàm backtrack để tìm tổng chi phí nhỏ nhất
            backtrack(0, new int[N]);

            // In kết quả cho từng test case
            System.out.println("#" + (t + 1) + " " + minCost);
        }

        sc.close();
    }

    // Hàm đệ quy để thử tất cả các cách mua thiết bị và gói ưu đãi
    private static void backtrack(int currentCost, int[] bought) {
        // Nếu chi phí hiện tại đã lớn hơn hoặc bằng minCost, dừng lại
        if (currentCost >= minCost) {
            return;
        }
        
        // Nếu đã mua đủ tất cả các thiết bị cần thiết
        if (allNeededBought(bought)) {
            minCost = Math.min(minCost, currentCost); // Cập nhật minCost
            return;
        }

        // Thử mua từng thiết bị ở chợ Trời
        for (int i = 0; i < N; i++) {
            if (bought[i] < needed[i]) { // Nếu vẫn cần mua thiết bị này
                bought[i]++;
                backtrack(currentCost + prices[i], bought); // Gọi đệ quy
                bought[i]--; // Quay lui (backtrack)
            }
        }

        // Thử mua từng gói ưu đãi
        for (int[] offer : offers) {
            int cost = offer[0]; // Giá của gói ưu đãi
            for (int i = 1; i < offer.length; i++) {
                bought[offer[i]]++; // Cập nhật số lượng thiết bị đã mua trong gói
            }
            backtrack(currentCost + cost, bought); // Gọi đệ quy
            for (int i = 1; i < offer.length; i++) {
                bought[offer[i]]--; // Quay lui (backtrack)
            }
        }
    }

    // Kiểm tra xem tất cả các thiết bị cần thiết đã được mua đủ chưa
    private static boolean allNeededBought(int[] bought) {
        for (int i = 0; i < N; i++) {
            if (bought[i] < needed[i]) { // Nếu thiết bị chưa mua đủ
                return false;
            }
        }
        return true; // Đã mua đủ tất cả các thiết bị
    }
}