// Johnny Boldt 
// Mar 17, 2011 
// johnny.boldt@gmail.com 

#include <iostream>

using namespace std;

const int NO_SOLUTION = -1;

const unsigned int MAX_GARMENTS = 20;
const unsigned int MAX_MODELS = 20;
const unsigned int MAX_MONEY = 200;

//Used for DP (Memoization)
bool visited[MAX_MONEY][MAX_GARMENTS];
int ammounts[MAX_MONEY][MAX_GARMENTS];

//Sets all prices to 0
void erasePrices(int prices[MAX_GARMENTS][MAX_MODELS]){
   for(int i = 0; i < MAX_GARMENTS; i++){
      for(int j = 0; j < MAX_MODELS; j++){
	 prices[i][j] = 0;
      }
   }
}

//Sets all prices to 0
void eraseVisited(bool  visited[MAX_MONEY][MAX_GARMENTS]){
   for(int i = 0; i < MAX_MONEY; i++){
      for(int j = 0; j < MAX_GARMENTS; j++){
	 visited[i][j] = false;
      }
   }
}

//Sets all prices to 0
void eraseAmmounts(int  ammounts[MAX_MONEY][MAX_GARMENTS]){
   for(int i = 0; i < MAX_MONEY; i++){
      for(int j = 0; j < MAX_GARMENTS; j++){
	 ammounts[i][j] = 0;
      }
   }
}

//Recursively finds maximum with memoization
int getMaximum(int prices[MAX_GARMENTS][MAX_MODELS], int M, int C){
   if(C < 0){ //If we have recursed past all garments, just return 0
      return 0;
   }
   if(M < 0){ //If we have used up all our money, no solution here
      return NO_SOLUTION;
   }
   if(visited[M][C]){ //Memoization
      return ammounts[M][C];
   }

   int maxFound = 0;
   for(int i = 0; i < MAX_MODELS; i++){
      if(prices[C][i] == 0){ //Since we initialize all prices to 0
		break;
      }
      int ammount = getMaximum(prices,M-prices[C][i],C-1);
      if(ammount != NO_SOLUTION){
		ammount +=  prices[C][i];	 
		if(M - ammount >= 0){
			maxFound = max(maxFound, ammount);
		}
      }
   }
   if(maxFound == 0){ //If we couldn't find any garmets, no solution was found
      return NO_SOLUTION;
   }
   //Memoization
   visited[M][C] = true;
   ammounts[M][C] = maxFound;
   
   return maxFound;
}

//Reads in input and outputs answer
//Array is 0 indexed, so called getMaximum with C-1
void do_case(){
   int prices[MAX_GARMENTS][MAX_MODELS];
   erasePrices(prices);
   eraseAmmounts(ammounts);
   eraseVisited(visited);
   int M, C;
   cin >> M >> C;
   
   for(int i = 0; i < C; i++){
      int K;
      cin >> K;
      for(int j = 0; j < K; j++){
	 cin >> prices[i][j];
      }
   }
   
   int answer = getMaximum(prices,M,C-1);
   if(answer == NO_SOLUTION){
      cout << "no solution" << endl;
   }
   else{
      cout << answer << endl;
   }
   return;
}

int main(){
   unsigned int N;
   cin >> N;
   while(N--){
      do_case();
   }
   return 0;
}