Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
17 kB
3
Indexable
Never
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.

*** test case
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

*** code
#include<iostream>
using namespace std;

int T, N, M, L, result;
int originPrize[25], packagePrize[35], packageCount[35], packageItem[35][25], needItem[25];
int cand[25][35], buyed[25];

void formatData() {
	result = 2000000000;
	for (int i = 1; i <= 20; i++) {
		buyed[i] = cand[i][0] = 0;
	}
}

void buy(int re, int count) {
	if (re > result) {
		return;
	}
	if (count == L + 1) {
		result = re < result ? re : result;
		return;
	}
	if (buyed[needItem[count]] > 0) {
		buy(re, count + 1);
	} else {
		buyed[needItem[count]]++;
	buy(re + originPrize[needItem[count]], count + 1);	
		buyed[needItem[count]]--;

		for (int c = 1; c <= cand[needItem[count]][0]; c++) {
			for (int n = 1; n <= packageCount[cand[needItem[count]][c]]; n++) {
				buyed[packageItem[cand[needItem[count]][c]][n]]++;
			}
			buy(re + packagePrize[cand[needItem[count]][c]], count + 1);
			for (int n = 1; n <= packageCount[cand[needItem[count]][c]]; n++) {
				buyed[packageItem[cand[needItem[count]][c]][n]]--;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		cin >> N;
		formatData();

		for (int i = 1; i <= N; i++) {
			cin >> originPrize[i];
		}
		cin >> M;
		for (int i = 1; i <= M; i++) {
			cin >> packagePrize[i] >> packageCount[i];
			for (int j = 1; j <= packageCount[i]; j++) {
				cin >> packageItem[i][j];
				cand[packageItem[i][j]][0]++;
				cand[packageItem[i][j]][cand[packageItem[i][j]][0]] = i;
			}
		}
		cin >> L;
		for (int i = 1; i <= L; i++) {
			cin >> needItem[i];
		}

		buy(0, 1);
		cout << "#" << tc << " " << result << endl;
	}
}