Bundles of Joy

Bob's Bakery has opened. The shop runs a "Bundles of Joy" sale that packs several desserts together so customers taste the whole menu.

For example, the chocolate cake bundle holds a chocolate layer cake and a black forest cake for $20. The fruity cake bundle holds a lemon pound cake and a key lime cake, also for $20. A larger bundle holds one slice of each of those four cakes for $38, which is less than the two smaller bundles together.

You want at least one of every dessert the bakery sells. So you have to buy some bundles, and you want to spend as little as possible.

The bundles have the following properties.

• For any two bundles $A$ and $B$, every dessert of $A$ is also in $B$, or every dessert of $B$ is also in $A$, or no dessert lies in both.
• The only way to buy a single dessert on its own is to buy a bundle of size 1. Not every dessert has such a bundle.
• The prices are not tidy. Buying some combination of other bundles can be cheaper than buying bundle $B$ itself, even when that combination holds everything in $B$.

The first line contains one integer $T$, the number of test cases ($1 \le T \le 50$). The first line of each test case contains two integers $n$ and $m$, where $n$ is the number of dessert types the bakery sells and $m$ is the number of bundles ($1 \le n \le 100$, $1 \le m \le 150$).

The next $m$ lines describe the bundles, one per line. Line $i$ begins with two integers $p_i$ and $s_i$, where $p_i$ is the price of bundle $i$ ($0 < p_i \le 10^6$) and $s_i$ is the number of desserts in it ($1 \le s_i \le n$). The rest of the line holds $s_i$ distinct integers between $1$ and $n$, the desserts included in bundle $i$.

Each of the $n$ desserts appears in at least one bundle.

For each test case, print one line with the minimum cost of buying bundles so that you end up with at least one of every dessert. This value fits in a 32-bit signed integer.