UVA_11495_Wedding_Solution

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <sstream>
#include <stdlib.h>
#include <cmath>
#define LL unsigned long long
using namespace std;

int main() {
    int g,money,k,TC,M,C;
    int price[25][25];
    bool reachable[25][210];
    scanf("%d",&TC);
    while(TC--){
        scanf("%d %d",&M,&C);
        for(g=0;g<C;g++){
            scanf("%d",&price[g][0]);
            for(money=1;money<=price[g][0];money++){
                scanf("%d",&price[g][money]);
            }
        }
        memset(reachable,false,sizeof reachable);
        for(g=1;g<=price[0][0];g++){/*casos bases*/
            if(M-price[0][g]>=0){
                reachable[0][M-price[0][g]]=true;
            }
        }
        for(g=1;g<C;g++)
         for(money=0;money<M;money++) if(reachable[g-1][money])
          for(k=1;k<=price[g][0];k++) if(money-price[g][k]>=0)
           reachable[g][money-price[g][k]]=true;
        for (money=0;money<=M && !reachable[C-1][money];money++);
        if(money==M+1) printf("no solution\n");
        else printf("%d\n",M-money);
    }
    return 0;
}