Q31: Shopping

Life is very convenient in year 5000, since you can get everything from the leading (and only) convenience store -- MicroStore. You need to buy a list of (distinct) gifts. To save money, you can buy some of the gifts in packages. MicroStore offers a range of gift packages for different prices. By smartly choosing which packages to buy, you can minimize the total cost while getting all the gifts. Assume the following:

• You can buy more than you need, as long as that makes it cheaper
• Everything you need is sold in one or more packages
• Packages only contain items you need (you would throw out the other unrelated items anyway)

Submit this problem in the judge as "Q31"

INPUT

There will be multiple test cases. The first line will contain an integer numCase equal to the number of test cases.
For each test case, the first line will contain two integers a b. 0 < a <= 15 is the number of gifts you need to buy, numbered from 0 to a-1. 0 < b <= 100 is the number of packages on sale. The following b lines describes the packages, and have the format:
p g1 g2 g3 ... gk
where p is the price, and g1 to gk are the gifts on sale (all integers, p <= 1000).
note The same package may be sold at several different prices (i.e. more expensive if previously by a celebrity). You of course don't care and would just buy it at the lowest price available.

OUTPUT

For each test case, output the least amount of money you need to spend to get all the shopping done.

Sample Input

3
3 3
4 0 1
3 1 2
2 0 2
5 1
100 0 1 2 3 4
3 3
1 0 1
1000 2
1 1 2

Sample Output

5
100
2