Nang cap may tinh

Level 4
Nâng cấp máy tính
Time limit: 1 giây với C/C++, 2 giây với Java.

Submission limit: 5 lần.

Memory limit: 256MB cho tổng cộng các vùng nhớ heap, global và static (chỉ 1MB cho vùng nhớ stack).



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.

Sample

Input

1          <-- T = 1,

5          <-- Số linh kiện chính của máy tính

20 15 17 18 25            <-- giá chợ Trời của 5 thiết bị từ 1 đến 5 tương ứng

4          <-- 4 gói ưu đãi trên mạng

30 3 1 2 5        <-- gói thứ nhất có giá 30, gồm 3 linh kiện 1, 2, 5

25 2 2 3           <-- gói thứ 2 có giá 25, gồm 2 linh kiện 2, 3

35 3 1 3 5        <-- gói thứ 3 có giá 35, gồm 3 linh kiện 1, 3, 5

20 2 3 4           <-- gói thứ 4 có giá 20, gồm 2 linh kiện 3, 4

3 2 4 5             <-- Số lượng anh Kim cần là 3, lần lượt là 2, 4, 5

Output

#1  48

Giải thích: Để mua được 3 thiết bị 2, 4, 5 với giá rẻ nhất, ta sẽ mua gói giá rẻ 1 gồm 1, 2, 5 với giá 30 và mua thiết bị 4 ở chợ Trời với giá 18, tổng là 30 + 18 = 48.


#1 176
#2 85
#3 80
#4 154
#5 3
#6 189
#7 99
#8 97
#9 209
#10 200
#11 79
#12 1
#13 197
#14 185
#15 23
#16 87
#17 29
#18 11
#19 140
#20 78
#21 211
#22 221
#23 120
#24 61
#25 91
#26 514
#27 180
#28 300
#29 165
#30 92
#31 165
#32 159
#33 173
#34 514
#35 628
#36 261
#37 171
#38 230
#39 55
#40 362
#41 26
#42 361
#43 122
#44 126
#45 465
#46 259
#47 72
#48 332
#49 280
#50 236
Time: 0.101000000 s.

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>
#include <stdio.h>
#define INT_MIN     (-2147483647 - 1) /* minimum (signed) int value */
#define INT_MAX       2147483647    /* maximum (signed) int value */
using namespace std;

template<typename T>
T maxv(T a, T b) {
	return a > b ? a : b;
}

template<typename T>
T minv(T a, T b) {
	return a < b ? a : b;
}

template<typename T>
void swapv(T &a, T &b) {
	T t = a;
	a = b;
	b = t;
}

template<typename T>
void fillWith(T a[], size_t n, const T &val) {
	for (size_t i = 0; i < n; ++i) {
		a[i] = val;
	}
}

const int oo = 999999999;
const int N = 22;
const int M = 32;
int tnum;
int n, m, ans;
int market[N]; // price
int package[M][N]; // package[i][0] is the price of package i
int have[N];

void input() {
	ans = oo;
	for (int i = 0; i < M; ++i) {
		fillWith(package[i], N, 0);
	}
	fillWith(have, N, -1);

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> market[i];
	}

	cin >> m;
	int nn, t;
	for (int i = 0; i < m; ++i) {
		cin >> package[i][0] >> nn;
		for (int k = 0; k < nn; ++k) {
			cin >> t;
			package[i][t] = 1;
		}
	}

	cin >> nn;
	for (int k = 0; k < nn; ++k) {
		cin >> t;
		have[t] = 0;
	}
}

void buyPackage(int i, int buy) {
	for (int j = 1; j <= n; ++j) {
		if (package[i][j] && have[j] >= 0 && have[j] + buy >= 0) {
			have[j] += buy;
		}
	}
}

void backtracking(int k=1, int curCost=0) {
	if (k > n) {
		ans = minv(ans, curCost);
		return;
	}

	if (curCost > ans) {
		return;
	}

	if (!have[k]) {
		// try to buy item k in online promotional package
		for (int i = 0; i < m; ++i) {
			// if package i has item k
			if (package[i][k]) {
				buyPackage(i, 1);
				backtracking(k + 1, curCost + package[i][0]);
				buyPackage(i, -1);
			}
		}

		// try to buy item k in flea market
		have[k] = 1;
		backtracking(k + 1, curCost + market[k]);
		have[k] = 0;

		//
	} else {
		backtracking(k + 1, curCost);
	}
}

void solve(int t) {
	input();
	backtracking();
	cout << "#" << t << " " << ans << endl;
}

int main() {
	int T = 10;

#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	clock_t t; 
    t = clock(); 
#endif
	
	cin >> T;
	for(tnum = 1; tnum <= T; ++tnum) {
		solve(tnum);
	}

#ifdef DEBUG
    t = clock() - t;
    double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds 
    printf("Finished in %f seconds\n", time_taken); 
#endif

	return 0;//Your program should return 0 on normal termination.
}