The Wedding

This week is Pride week.  To celebrate it, Desmond and Christopher are
getting married.  You want to attend the wedding, but you don't have
the appropriate clthes.  So you decide to go to the Rolt Henfrew to
buy all that you need:  a shirt, a belt, a pair of shoes, a waistcoat,
a hat, a tie, etc.

Rolt Henfrew offers different options for each class of garment (for
example, seven kinds of shirts, four kinds of belts, ...).  You have
to buy one item of each class of garment, and just one. 

You have a limited number of dollars to spend, but you want to spend
the maximum possible, since you want to look fabulous at the wedding.
It's possible that we cannot buy one model of each class of garment
due to the short amount of money we have.  (Then you will have to go
to a cheaper store instead of Rolt Henfrew.) 

The Input

The first line of the input contains an integer, N, indicating the
number of test cases. For each test case, some lines appear, the first
one contains two integers, M and C, separated by blanks (1<=M<=200,
and 1<=C<=20), where M is the available amount of money and C is the
number of garments you have to buy. Following this line, there are C
lines, each one with some integers separated by blanks; in each of
these lines the first integer, K (1<=K<=20), indicates the number of
different kinds of each garment and it is followed by K positive integers
indicating the price of each item of that garment class. 

The Output

For each test case, the output should consist of one integer
indicating the maximum amount of money that can be spent to buy one
item of each garment class without exceeding the initial amount of
money. If there is no solution, you must print "no solution".

Sample Input

3
100 4
3 8 6 4
2 5 10
4 1 3 3 7
4 50 14 23 8
20 3
3 4 6 8
2 5 10
4 1 3 5 5
5 3
3 6 4 8
2 10 6
4 7 3 1 7

Sample Output

75
19
no solution