Wedding shopping

#include <bits/stdc++.h>
using namespace std;

int M, C;
int price[30][30];
int dp[30][300];
int sz[30];

/* dp[i][j] = 1, se for possivel pegar exatamente 1 item de cada linha
                 considerando até a linha atual de tal forma que resta
                 j unidades de dinheiro

              0, caso contrario
*/

int main() {

    int t;
    cin >> t;
    while(t--) {
        cin >> M >> C;

        for(int i = 0; i < C; i++) {
            cin >> sz[i];
            for(int j = 0; j < sz[i]; j++)
                cin >> price[i][j];
        }

        memset(dp, 0, sizeof(dp));

        for(int i = 0; i < sz[0]; i++)
            if(M - price[0][i] >= 0)
                dp[0][ M - price[0][i] ] = 1;

        for(int i = 1; i < C; i++)
            for(int money = 0; money <= M; money++)
                if(dp[i - 1][money])
                    for(int k = 0; k < sz[i]; k++)
                        if(money - price[i][k] >= 0)
                            dp[i][ money - price[i][k] ] = 1;

        int ans = -1;
        for(int money = 0; money <= M; money++)
            if(dp[C - 1][money])
                ans = max(ans, M - money);

        if(ans == -1) cout << "no solution\n";
        else cout << ans << '\n';
    }

    return 0;
}