Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
18 kB
0
Indexable
Never
Anh Kim có 1 máy tính đã mua từ thời sinh viên nên hiện giờ cần phải nâng cấp và thay thế L linh kiện để đảm bảo máy tính hoạt động tốt.

Để tìm mua được các thiết bị đó với giá tốt nhất anh Kim đã qua chợ Trời và tham khảo được giá của tất cả N thiết bị của máy tính.

Không chỉ thế, anh đã tìm kiếm thêm trên mạng, và anh rất vui khi có M gói ưu đãi giá rẻ được rao bán trên mạng, mỗi gói có giá bán là P bao gồm K thiết bị của máy tính.

Anh Kim có thể mua một hoặc nhiều gói ưu đãi và có thể mua thừa linh kiện chưa cần thay thế.

Hãy giúp anh Kim mua được đủ L thiết bị cần thiết với tổng giá thành là nhỏ nhất.


Input
Dòng đầu tiên là số lượng test case T (T <= 50).

Mỗi test case gồm các thông tin sau:

- Dòng đầu tiên là số nguyên dương N (1 <= N <= 20) là số lượng thiết bị chính của máy tính.

- Dòng thứ 2 bao gồm N số, số thứ i tương ứng là giá của thiết bị thứ i được bán ở chợ Trời.

- Dòng thứ 3 là số nguyên dương M ( 0 <= M <= 30) là số lượng gói ưu đãi có trên mạng.

- M dòng tiếp theo, mỗi dòng thứ i là thông tin về gói ưu đãi thứ i. Số đầu tiên là giá của gói ưu đãi P ( 1 <= P <= 1000), số tiếp theo là số lượng thiết bị K ( 1 <= K< = N) trong gói ưu đãi đó,

K số tiếp theo là các thiết bị có trong gói ưu đãi đó.

- Dòng cuối cùng của mỗi test case là thông tin về các thiết bị mà anh Kim cần mua. Số đầu tiên là số lượng thiết bị L, L số tiếp theo là các thiết bị anh Kim cần mua

- Các thiết bị được đánh số trong đoạn từ 1 đến N và không có số nào trùng nhau



Output
Bắt đầu mỗi test case là "#x" với x là số thứ tự của test case (bắt đầu từ 1), tiếp theo là một dấu cách và giá thành nhỏ nhất mà anh Kim cần bỏ ra để mua đủ những thiết bị anh cần.

50
10
68 63 83 94 55 35 12 63 30 17 
4
104 3 2 6 3 
31 3 2 5 3 
81 4 3 2 7 9 
42 1 7 
6 9 10 3 8 6 5 
4
40 52 12 94 
2
58 2 1 4 
15 1 2 
3 4 2 3 
8
61 91 11 32 33 59 77 24 
5
81 2 2 3 
13 3 6 2 5 
78 2 5 3 
9 1 7 
9 1 5 
4 8 3 4 2 
11
61 9 82 30 86 58 34 31 19 30 93 
12
24 2 3 8 
151 3 11 4 9 
142 3 7 3 10 
18 2 7 6 
207 5 8 5 7 2 11 
65 2 11 8 
16 3 3 1 11 
36 1 2 
150 4 10 7 2 8 
3 1 8 
20 1 2 
138 5 11 5 8 6 7 
6 3 10 9 1 5 8 
3
11 72 66 
8
8 1 2 
3 1 1 
18 1 2 
32 1 3 
19 1 3 
28 1 2 
34 1 2 
15 1 2 
1 1 
6
32 4 11 99 24 55 
3
40 1 1 
111 3 6 3 2 
73 2 1 5 
4 3 6 5 4 
9
66 61 18 58 34 75 29 36 66 
6
62 2 1 4 
32 1 4 
22 3 5 3 1 
10 1 9 
25 1 9 
6 4 6 1 7 8 
6 2 9 8 7 5 3 
4
78 46 92 82 
14
68 2 3 2 
129 2 2 1 
28 1 4 
134 2 1 4 
56 2 2 3 
56 2 4 2 
66 1 2 
68 1 4 
37 1 2 
41 1 3 
36 2 4 2 
85 2 1 2 
19 2 2 3 
38 1 2 
2 1 3 
4
57 86 72 66 
0
3 1 4 2 
7
93 58 20 97 20 6 90 
5
122 3 1 4 7 
107 3 4 5 2 
18 1 6 
53 3 1 5 4 
18 1 1 
5 7 2 1 4 3 
5
36 52 59 44 35 
4
43 1 2 
79 2 1 4 
60 2 3 2 
5 1 3 
2 4 5 
3
45 11 21 
10
20 1 2 
1 1 3 
9 1 3 
5 1 2 
11 1 2 
3 1 1 
5 1 2 
8 1 2 
28 1 2 
23 1 3 
1 3 
10
88 37 61 62 59 64 23 76 21 52 
13
122 3 9 4 1 
59 3 4 7 8 
44 2 6 5 
47 1 7 
23 1 2 
40 2 8 4 
37 1 5 
164 4 1 2 3 10 
2 1 9 
158 4 8 1 9 10 
17 4 8 5 9 4 
38 3 1 9 4 
236 5 1 2 5 6 7 
7 1 4 6 7 8 2 10 
9
17 15 46 85 3 84 70 73 74 
2
48 2 5 4 
86 4 7 3 8 4 
4 2 6 3 7 
4
69 79 23 69 
10
9 2 3 4 
82 2 4 2 
21 2 3 2 
85 2 3 4 
56 2 3 2 
49 1 2 
2 1 3 
21 1 1 
16 2 4 3 
21 1 2 
2 3 1 
9
42 8 84 75 48 17 28 83 96 
13
66 4 9 7 2 3 
154 3 7 8 4 
88 3 2 4 9 
24 4 6 1 2 5 
86 4 7 8 4 9 
30 1 2 
6 4 3 2 4 6 
46 2 2 8 
73 2 4 2 
175 4 5 2 8 4 
11 3 6 7 9 
96 2 1 6 
20 3 4 7 6 
6 6 7 5 9 4 8 
8
55 7 38 12 61 22 86 2 
10
34 1 4 
25 2 3 7 
39 2 8 2 
17 2 2 5 
77 2 7 2 
13 4 1 8 3 4 
32 2 8 1 
24 2 6 5 
4 4 1 8 6 2 
122 4 2 5 7 1 
4 6 7 3 1 
3
73 47 79 
14
41 1 1 
18 1 1 
46 1 2 
11 1 2 
21 1 2 
31 1 1 
30 1 2 
7 1 3 
47 1 3 
10 1 3 
22 1 3 
25 1 2 
54 1 2 
23 1 1 
1 2 
6
98 85 36 26 55 40 
5
5 2 5 6 
16 1 3 
56 1 2 
33 1 5 
21 1 5 
3 4 3 1 
5
10 68 3 69 1 
3
30 1 3 
20 2 4 1 
4 1 4 
2 1 2 
14
43 81 53 97 77 1 95 91 84 43 57 93 70 65 
16
23 1 11 
11 3 2 8 10 
45 3 10 2 7 
179 4 3 12 13 4 
14 5 8 12 4 14 2 
1 3 14 1 12 
56 4 4 5 2 1 
6 1 9 
131 7 13 9 10 4 14 3 2 
213 5 3 11 4 13 6 
254 6 14 1 13 5 4 10 
92 2 8 6 
86 2 11 8 
48 3 7 9 6 
179 4 9 14 12 3 
74 3 8 6 7 
12 13 7 9 10 4 1 11 3 2 8 12 14 
14
55 92 13 59 30 53 19 23 50 99 58 80 26 94 
21
126 6 9 5 6 11 2 7 
43 1 4 
27 7 11 10 3 14 4 6 5 
141 4 1 6 7 11 
249 6 4 6 8 3 9 11 
61 6 13 10 9 8 12 6 
366 7 3 4 13 6 7 11 12 
267 7 6 7 14 5 4 12 9 
171 4 5 7 11 12 
56 1 12 
98 2 14 6 
75 5 13 10 1 14 11 
5 1 6 
51 5 4 1 12 8 5 
97 5 12 5 4 7 13 
8 4 14 12 10 9 
272 7 7 3 4 2 11 6 9 
77 5 13 5 6 11 4 
20 6 10 4 6 8 12 5 
48 7 6 5 11 10 3 14 12 
190 5 2 9 7 3 6 
11 9 7 3 2 13 5 11 10 12 4 1 
13
95 88 64 1 73 31 9 62 7 23 90 76 64 
17
115 3 1 8 9 
40 1 8 
165 5 3 4 10 5 1 
29 1 6 
188 5 11 7 9 3 4 
15 2 4 11 
165 6 10 4 9 3 8 2 
142 3 9 13 6 
47 4 13 10 12 9 
8 1 7 
51 6 12 11 10 4 8 6 
95 4 6 2 7 12 
25 1 6 
70 5 13 12 10 6 1 
18 2 6 4 
38 1 12 
54 6 5 1 13 4 3 10 
11 3 5 8 7 1 12 9 10 11 6 13 
13
21 1 28 39 18 17 49 1 51 80 4 86 46 
18
92 4 10 8 12 3 
2 2 5 8 
8 1 2 
34 5 11 9 6 12 7 
31 2 4 8 
163 5 10 12 8 6 7 
94 3 13 7 2 
24 6 12 7 10 8 1 9 
50 2 5 4 
27 1 6 
4 3 10 6 13 
126 6 10 8 1 5 6 4 
13 4 1 8 12 4 
65 2 8 10 
10 1 4 
19 3 6 9 5 
41 1 8 
11 5 5 7 6 9 4 
11 3 12 7 8 5 4 1 11 2 6 10 
16
26 40 28 91 6 33 14 14 53 78 58 44 73 5 59 79 
14
54 2 8 1 
79 5 3 12 10 15 8 
82 2 4 7 
154 5 4 9 14 6 13 
170 4 11 9 16 8 
283 6 13 4 11 1 15 10 
230 6 13 3 16 14 1 6 
24 4 6 10 1 5 
152 5 16 11 3 12 5 
90 2 10 2 
195 6 7 15 13 4 12 14 
24 3 2 15 6 
42 6 7 3 16 9 1 11 
131 3 10 16 12 
9 16 2 11 8 1 15 5 14 7 
17
49 14 10 49 96 65 30 71 58 76 81 41 30 41 81 71 47 
5
288 6 2 10 7 4 8 9 
32 3 4 11 12 
45 1 7 
61 4 3 9 8 12 
102 2 14 5 
13 10 7 14 4 9 6 12 16 3 5 13 17 11 
11
87 56 8 80 47 20 29 46 50 31 66 
5
7 1 9 
30 4 11 2 5 3 
36 1 11 
47 4 2 9 3 4 
36 5 11 5 2 9 1 
8 4 3 11 6 1 8 10 5 
15
25 77 72 41 86 41 28 82 6 11 47 16 10 51 48 
1
93 3 14 6 15 
7 2 14 10 8 7 4 13 
13
24 62 28 37 88 62 27 5 2 22 88 93 77 
17
9 4 13 10 1 12 
197 5 8 3 13 11 7 
92 4 7 1 4 13 
20 2 6 12 
113 4 7 9 6 3 
165 5 5 13 10 2 9 
61 2 8 4 
183 4 5 6 11 13 
4 5 6 13 9 1 2 
75 2 1 6 
81 6 8 7 2 9 1 4 
176 5 4 6 2 9 8 
75 3 4 6 10 
46 1 7 
88 2 13 8 
42 2 12 1 
34 2 13 5 
9 11 10 7 12 2 9 4 1 6 
11
27 17 58 87 28 97 29 30 57 96 39 
21
8 3 5 10 11 
34 5 7 4 2 10 5 
105 3 11 2 6 
126 4 2 7 6 3 
53 4 5 4 6 10 
83 3 10 5 3 
20 2 11 2 
76 2 10 1 
89 2 1 2 
19 1 6 
4 4 6 3 5 2 
145 4 5 1 11 9 
110 4 4 11 5 10 
180 4 3 4 5 10 
10 1 9 
264 5 8 9 2 5 4 
62 4 11 10 5 9 
9 1 3 
19 2 1 3 
98 3 10 7 1 
25 5 2 10 4 3 7 
7 11 8 2 1 9 4 5 
17
26 67 98 58 8 61 83 45 85 14 55 7 6 28 13 47 9 
20
334 8 11 13 6 10 3 1 16 8 
136 4 4 14 6 17 
127 3 9 2 5 
36 3 4 16 15 
70 4 17 4 1 16 
27 8 14 5 3 11 6 10 13 7 
43 2 12 17 
103 4 7 4 8 9 
108 6 7 8 15 3 9 5 
52 2 17 6 
97 4 6 7 1 9 
46 1 6 
144 3 3 17 1 
141 8 9 12 6 5 17 3 8 2 
99 8 8 9 3 16 14 4 10 2 
175 8 13 11 2 1 3 8 7 4 
288 7 2 7 14 3 15 16 6 
103 2 10 2 
159 5 14 10 6 12 7 
13 2 5 7 
13 5 14 16 11 13 2 3 4 1 8 9 10 15 
19
75 29 39 37 75 69 3 79 95 50 94 14 33 88 9 69 34 95 78 
28
370 9 5 9 13 1 15 10 17 3 11 
160 6 2 14 9 4 7 12 
47 1 8 
100 3 17 8 9 
338 7 12 17 11 2 10 5 3 
86 4 4 11 15 7 
41 1 10 
96 2 1 11 
185 5 17 18 1 7 2 
37 1 13 
254 8 10 14 19 1 7 12 6 13 
60 2 16 19 
27 1 5 
202 5 17 4 13 3 14 
117 6 18 11 16 17 19 7 
91 4 18 5 16 13 
164 6 7 2 10 14 13 19 
94 3 9 13 3 
39 2 6 13 
237 5 8 14 11 1 16 
173 4 6 14 4 5 
171 6 7 5 13 2 11 4 
76 2 19 5 
21 6 9 15 14 3 19 10 
25 2 19 9 
26 8 4 18 3 9 8 13 1 17 
211 7 13 17 9 2 14 10 15 
174 4 11 10 3 19 
13 2 8 10 15 9 3 1 12 5 18 6 7 13 
13
74 14 1 44 93 77 80 76 96 88 80 95 46 
15
6 4 6 4 12 7 
50 2 3 8 
5 1 6 
136 5 10 6 12 2 7 
103 6 13 2 9 1 7 8 
190 5 7 2 1 3 12 
167 4 2 7 11 1 
89 3 3 8 11 
55 4 1 7 2 10 
115 6 2 6 4 1 9 8 
42 5 3 13 2 6 9 
18 5 5 6 4 7 9 
147 6 9 2 5 3 10 6 
209 6 12 13 3 10 1 5 
112 6 12 11 10 13 8 2 
8 1 3 12 6 11 13 2 7 
16
57 37 39 8 25 26 63 85 24 12 40 34 2 28 68 15 
0
14 15 7 3 6 9 1 13 16 14 5 4 12 8 11 
18
9 17 68 80 94 86 9 87 28 96 35 87 61 99 95 54 52 45 
4
89 6 4 13 6 3 18 14 
103 2 4 9 
389 8 8 16 1 15 7 18 17 11 
279 7 4 11 6 1 2 13 5 
15 8 12 3 4 1 11 16 14 6 7 17 2 15 13 5 
12
50 31 70 44 94 35 68 57 2 46 99 75 
14
84 3 1 10 8 
187 6 8 10 7 2 9 1 
217 5 2 5 4 12 7 
177 4 3 1 10 8 
217 6 3 7 4 8 5 12 
131 6 10 4 9 7 6 3 
172 5 9 1 3 6 5 
1 4 9 5 4 1 
44 2 10 2 
73 4 11 1 6 4 
47 3 9 5 2 
24 3 9 7 3 
82 2 11 8 
42 3 5 4 6 
11 10 7 11 6 12 1 8 2 9 4 5 
12
79 39 87 87 20 54 44 88 70 58 14 66 
7
67 3 7 3 5 
48 2 9 1 
2 1 4 
12 2 6 4 
73 6 1 6 11 3 9 7 
18 1 3 
68 6 1 12 6 10 9 11 
9 10 3 6 1 7 11 4 2 9 
17
46 6 41 98 77 19 82 20 24 13 33 83 24 7 68 27 38 
3
88 2 10 7 
233 5 8 2 1 5 13 
77 3 5 6 10 
8 7 3 16 2 9 8 10 13 
14
42 27 19 12 59 88 93 39 35 78 39 81 26 81 
15
18 1 4 
3 3 9 7 1 
16 5 9 8 2 10 14 
120 3 2 14 9 
34 1 4 
38 7 13 14 5 4 3 10 2 
95 5 9 7 11 14 10 
17 1 11 
156 7 6 7 8 11 3 5 9 
34 1 6 
13 2 6 9 
51 4 11 7 6 10 
182 5 7 12 9 6 1 
49 2 1 4 
58 4 9 8 12 6 
7 2 11 3 7 14 10 8 
19
87 35 43 52 35 88 79 32 85 56 6 79 34 58 27 24 76 70 61 
18
110 6 16 6 17 9 7 4 
183 6 5 15 19 14 1 2 
25 1 3 
1 1 7 
367 8 19 14 8 16 18 7 17 1 
116 3 4 14 18 
165 5 19 18 17 1 13 
32 1 2 
8 1 7 
96 3 17 13 7 
52 3 17 10 18 
20 1 1 
23 3 3 16 1 
28 1 7 
135 6 15 4 18 7 14 9 
21 1 16 
45 1 7 
222 5 17 10 6 1 3 
12 15 13 16 9 17 6 4 18 10 1 14 19 
11
43 9 61 10 33 57 51 72 49 69 95 
29
200 4 8 3 5 9 
11 4 2 1 7 11 
36 2 7 2 
57 2 9 5 
78 2 9 2 
20 4 1 7 5 6 
107 3 11 9 3 
4 3 8 6 11 
1 2 6 10 
25 4 11 6 10 7 
99 5 1 7 3 10 5 
236 5 8 6 3 9 4 
76 2 3 2 
95 4 9 6 1 8 
74 4 11 7 3 8 
170 4 10 1 5 3 
79 3 9 1 7 
32 1 7 
91 3 11 3 8 
163 4 10 3 9 11 
99 5 4 2 9 7 8 
209 5 3 6 10 9 11 
182 4 2 11 1 3 
91 2 4 3 
28 1 5 
143 4 8 1 10 9 
22 1 11 
25 1 5 
14 2 4 11 
5 7 8 10 1 4 
16
31 65 17 70 28 16 67 27 86 97 6 63 72 71 46 26 
22
23 2 13 6 
3 2 15 14 
222 5 14 8 10 4 6 
16 1 13 
33 1 14 
165 7 12 9 1 11 7 13 6 
33 3 2 5 12 
106 4 1 14 9 15 
130 3 6 4 16 
78 2 15 13 
93 3 6 5 10 
3 2 5 2 
295 8 14 2 15 13 4 8 3 12 
9 3 9 11 2 
22 1 9 
227 7 8 6 12 7 1 14 4 
34 1 5 
132 3 8 2 10 
41 1 4 
95 2 15 1 
92 5 5 6 4 14 8 
7 1 9 
15 5 3 13 4 16 8 10 6 7 2 14 15 9 12 1 
15
96 5 67 21 87 5 37 17 93 42 50 53 58 47 81 
22
6 1 2 
100 5 1 9 11 13 5 
226 5 12 6 4 9 3 
96 2 8 2 
254 6 14 6 12 10 5 15 
210 6 13 15 11 2 7 4 
28 3 8 12 10 
31 3 1 5 11 
24 1 12 
37 1 3 
194 6 15 12 8 11 6 4 
207 7 10 9 7 1 12 11 6 
248 6 4 7 10 6 9 2 
51 4 15 9 2 1 
7 3 14 7 13 
258 7 14 10 15 11 7 6 13 
47 3 8 1 13 
47 3 3 8 5 
96 4 7 5 1 12 
77 2 8 10 
13 4 7 15 8 6 
63 5 5 2 11 6 14 
9 2 8 15 9 6 5 10 1 14 
12
5 1 51 19 97 13 74 51 57 29 92 47 
22
27 3 3 9 2 
27 1 4 
258 6 8 6 3 9 1 10 
32 6 8 4 9 3 1 5 
178 4 11 6 8 7 
30 2 11 2 
188 5 9 2 8 7 3 
160 4 12 9 7 10 
2 1 7 
33 1 5 
130 5 1 2 6 10 7 
43 2 5 7 
45 5 7 6 9 8 3 
86 2 2 4 
86 2 1 10 
33 1 9 
48 1 6 
23 3 12 7 5 
167 6 10 4 1 6 11 5 
69 6 2 11 6 3 9 8 
54 2 1 9 
124 3 5 7 3 
7 5 11 12 10 1 6 3 
13
56 43 99 36 77 59 50 53 21 34 67 16 84 
6
64 2 12 11 
76 4 1 10 13 4 
268 6 10 11 4 13 1 8 
242 6 7 11 6 1 5 13 
88 2 6 4 
268 6 2 3 6 4 13 10 
9 2 9 6 7 10 8 11 3 1 
16
19 31 19 46 23 88 60 20 13 80 19 85 71 12 71 87 
10
48 1 6 
253 6 8 3 11 12 14 9 
37 1 9 
16 1 2 
42 6 8 16 1 13 10 2 
309 8 8 12 11 10 13 15 5 1 
146 3 2 3 6 
39 1 4 
5 2 2 10 
42 4 8 6 2 1 
11 2 3 13 1 8 9 7 11 14 5 15 
12
95 67 33 90 5 94 72 3 63 60 79 18 
27
224 5 2 11 8 3 10 
64 5 8 5 6 1 10 
121 4 3 4 11 1 
134 5 2 11 1 7 3 
79 5 7 9 12 8 5 
34 1 12 
12 1 9 
111 5 8 3 12 7 4 
39 1 9 
44 4 9 8 1 11 
120 4 2 6 11 10 
36 6 4 9 7 2 10 1 
96 2 7 6 
131 4 10 4 6 12 
14 2 3 5 
28 3 5 6 9 
22 5 9 12 5 6 7 
137 5 11 12 9 2 7 
39 4 5 4 2 7 
50 3 4 5 3 
49 4 7 12 8 2 
83 2 8 4 
118 3 9 5 4 
143 5 12 11 3 1 2 
132 5 5 6 10 9 1 
120 5 11 1 3 7 10 
46 1 8 
7 10 3 4 2 12 9 6 
14
92 81 27 38 74 84 74 80 69 12 90 97 24 20 
11
139 4 5 13 1 10 
71 5 5 1 11 3 14 
72 3 4 8 12 
215 4 9 10 2 6 
45 1 2 
54 5 13 1 4 10 12 
101 4 2 14 9 10 
82 2 12 3 
262 7 8 2 14 1 4 11 9 
158 5 11 12 2 9 14 
52 4 8 12 14 7 
13 11 8 9 12 5 7 14 2 13 3 6 10 1 
13
35 33 87 28 86 34 80 40 14 17 37 31 21 
7
268 6 8 10 13 9 7 2 
92 2 10 2 
27 1 6 
19 2 10 13 
7 1 7 
135 3 7 11 6 
90 5 1 8 10 9 6 
9 12 6 2 10 7 5 11 8 13 
20
50 42 21 81 91 9 83 96 39 33 46 12 75 21 65 62 7 58 39 55 
13
310 7 3 17 5 10 13 7 16 
321 7 13 20 16 18 5 15 4 
125 5 3 2 14 18 1 
201 6 6 2 3 9 16 7 
27 1 9 
403 10 18 14 9 15 3 17 4 11 13 10 
196 4 20 3 10 15 
45 10 19 15 7 4 13 9 14 8 18 16 
152 10 5 20 2 8 17 13 6 9 12 16 
6 6 17 13 19 10 1 5 
47 1 7 
182 4 15 12 9 19 
255 5 18 14 3 5 4 
12 6 12 3 5 10 16 11 7 9 2 20 4 



#include<iostream>

using namespace std;

int list_components[3][21]; //gia lk tuong ung + need or not + visited components need
int list_offers[30][23];    //danh sach cac goi uu dai

int n; //so luong thiet bi chinh cua may tinh
int m; //so goi uu dai co tren thi truong
int price_max, price_offer, price_market, total, _cnt;
int visited[30];

int k, jj;

//check goi uu dai co lk can mua khong && da mua truoc do hay chua
bool check(int m){
    for(int i=0; i<list_offers[m][1]; i++){
        if(list_components[1][list_offers[m][2+i]] == 1 && list_components[2][list_offers[m][2+i]] == 0)
            return true;
    }
    return false;
}

//k la goi lua chon
void backtrack(int k){
    if(price_offer>= price_max && k>0) return;
    if(total < price_max && total > 0) price_max = total;
    if(k==m){
        price_market = 0;
        for(int i=1; i<=n; i++){
            if(list_components[1][i]==1 && list_components[2][i]==0)
                price_market+=list_components[0][i];
        }
        total = price_offer+price_market;
        if(total < price_max) price_max = total;
        	return;
    }

    if(check(k)){
        //danh dau component co trong goi uu dai
        for(int i=0; i<list_offers[k][1]; i++){
            list_components[2][list_offers[k][2+i]] = 1;
        }
        //cong gia goi uu dai
        price_offer+=list_offers[k][0];
        //cong lk khong co trong uu dai
        price_market = 0;
        for(int i=1; i<=n; i++){
            if(list_components[1][i]==1 && list_components[2][i]==0)
                price_market+=list_components[0][i];
        }
        total = price_offer+price_market;
        //backtrack
        backtrack(k+1);
        //danh dau component co trong goi uu dai
        for(int i=0; i<list_offers[k][1]; i++){
            list_components[2][list_offers[k][2+i]] = 0;
        }
        //cong gia goi uu dai
        price_offer-=list_offers[k][0];
        //cong lk khong co trong uu dai
        price_market = 0;
        for(int i=1; i<=n; i++){
            if(list_components[1][i]==1 && list_components[2][i]==0)
                price_market+=list_components[0][i];
        }
        total = price_offer + price_market;
    }
    backtrack(k+1);
}

int main()
{
    ios:: sync_with_stdio(false); 
    cin.tie(NULL);

    int T;
    freopen("input.txt", "r", stdin);
    cin >> T;
    for(int test_case = 1; test_case <= T; ++test_case)
    {
        //reset
        for(int i=0; i<3; i++)
            for(int j=0; j<21; j++)
                list_components[i][j]=0;
        for(int i=0; i<30; i++)
            for(int j=0; j<23; j++)
                list_offers[i][j]=0;
        //input
        cin >> n;
        for(int i=1; i<=n; i++)
            cin >> list_components[0][i];

        cin >> m;
        for(int i=0; i<m; i++){
            cin >> list_offers[i][0] >> list_offers[i][1];
            for(int j=2; j<=list_offers[i][1]+1; j++)
                cin >> list_offers[i][j];
        }

        cin >> jj;
        for(int i=1; i<=jj; i++){
            cin >> k;
            list_components[1][k] = 1;
        }
        //process
        //tinh price_max
        price_max = 0;
        price_offer = 0;
        for(int i=1; i<=n; i++){
            if(list_components[1][i]==1)
                price_max+=list_components[0][i];
        }

        if(m==0)
            cout << "#" << test_case << " " << price_max << endl;
        else {
            total = 0;
            backtrack(0);
            cout << "#" << test_case << " " << price_max << endl;
        }
    }
    return 0;//Your program should return 0 on normal termination.
}