Problem E
Bundles of Joy

For example, you can buy the “Chocolate Cakes” bundle which includes chocolate layer cake and black forest cake for $20. Or you can buy the “Fruity Cakes” bundle which includes lemon pound cake and key lime cake, also for $20. They offer an even bigger bundle that includes a slice of each of these cakes for an even lower price of $38.

You want to try out each dessert they offer. So, you need to buy some bundles to ensure you get at least one of each dessert. Of course, your goal is to do this while minimizing the amount of money you spend on bundles.

Finally, you make a few observations about the bundles they offer:

• For any two bundles $A$ and $B$, either every dessert in $A$ is also in $B$, every dessert in $B$ is also in $A$, or there is no dessert in both $A$ and $B$.

• The only way to buy an item individually is if it is in a bundle of size 1. Not all items are in such a bundle.

• The pricing is not very well thought out. It may be cheaper to acquire items in a bundle $B$ by buying some combination of other bundles rather than $B$ itself.

Input

The first line contains a single integer $T \leq 50$ indicating the number of test cases. The first line of each test case contains two integers $n$ and $m$ where $n$ is the number of different types of desserts offered by Bob’s Bakery and $m$ is the number of different bundles. Here, $1 \leq n \leq 100$ and $1 \leq m \leq 150$.

Then $m$ lines follow, each describing a bundle. The $i$th such line begins with two positive integers $p_ i$ and $s_ i$. Here, $0 < p_ i \leq 10^6$ is the price of bundle $i$ and $1 \leq s_ i \leq n$ is the number of items in bundle $i$. The rest of this line consists of $s_ i$ distinct integers ranging from $1$ to $n$, indicating what desserts are included in this bundle.

Each of the $n$ items will appear in at least one bundle.

Output

The output for each test case is a single line containing the minimum cost of purchasing bundles to ensure you get at least one of each item. This value is guaranteed to fit in a 32-bit signed integer.

4
4 3
20 2 1 2
20 2 3 4
38 4 1 2 3 4
2 3
5 1 1
10 2 1 2
4 1 2
2 2
1 1 1
5 2 2 1
1 2
2 1 1
1 1 1

38
9
5
1