Fixing Open Source Bugs

Time limit4sMemory limit256 MB

Summary

Given bugs with fun values and prerequisite dependencies, choose a set of bugs to fix (each with all its prerequisites) that maximizes total fun.

Level: Medium7 of 10
Topics: Graph, Dynamic programming, Greedy, Topological sort
Solved: No attempts yet

Problem

As a hobby, you sometimes fix bugs in the open source SDK "Le Great SDK" (LG SDK). A batch of recently found bugs and the dependencies between them have landed you a fun problem to solve.

There are currently n reported bugs, and after reading each bug report you rated how fun it would be to fix that bug. The bugs are numbered 1 through n.

Specifically, fixing bug i gives you f_i units of fun. This value is a positive or negative integer. A negative value means the bug is so boring that you do not enjoy the process of fixing it.

It would be nice if you could fix only the bugs with positive fun, but reading the reports revealed that some bugs require fixing other bugs first. That is, to fix bug i you may have to fix some other bug j as well, whether you want to or not, before bug i counts as fully fixed.

For example, suppose n = 3 bugs are reported with fun values f_1 = 5, f_2 = -2, f_3 = 3. To fix bug 1 you must also fix bug 2, and fixing bug 2 requires no other bugs. Finally, to fix bug 3 you must fix both bugs 1 and 2.

In this case, fixing only bug 2 gives a total fun of -2, while fixing bugs 1 and 2 gives a total fun of 3, which is positive. Fixing all three bugs gives a total fun of 6.

Given the number of bugs, the fun value of each bug, and the dependencies between bugs, you want to fix only the bugs that maximize your fun. Find the maximum total fun you can achieve.

Input

The first line gives the number of test cases T.

The first line of each test case gives the number of bugs n. The second line gives n integers separated by spaces, the fun value f_i of each bug.

The next n lines each contain one or more integers. The first integer on line i is how many other bugs must be fixed to fix bug i. If that number is x_i, then x_i more space-separated integers follow on the same line, naming the other bugs that must be fixed together with bug i. The x_i bugs given are distinct.

Output

For each test case, print the maximum total fun on a line.

Constraints

1 ≤ T ≤ 10
2 ≤ n ≤ 500
1 ≤ |f_i| ≤ 1,000,000
0 ≤ x_i ≤ min(300, n-1)

Examples1

Example 1

Input

8
4
2 -3 6 -4
1 2
0
2 2 4
1 2
3
2 -6 3
0
0
2 1 2
3
5 -2 3
1 2
0
2 1 2
3
-2 -3 -4
0
0
0
3
1 -1 2
1 2
1 3
1 1
6
-51 -89 -58 21 -6 35
0
4 1 4 3 5
2 4 6
1 1
4 1 4 6 3
1 1
5
-10 -10 -10 -10 39
0
0
0
0
4 1 2 3 4
7
72 96 -45 -69 -46 65 -70
0
1 1
2 1 2
3 1 2 3
2 1 2
4 1 2 3 5
2 3 5

Expected output