SanXuat

#include <bits/stdc++.h>

using namespace std;

int n, m, t[1003][1003];

int SanXuat(int i, int c) {
    if (c < 0) return(-1);
    if (i > n) return(m - c);
    int res = -1;
    for (int j=1; j<=t[i][0]; ++j)
        res = max(res, SanXuat(i+1, c-t[i][j]));
    return(res);
}

int main() {
    freopen("SanXuat.inp", "r", stdin);

    int test; scanf("%d", &test);
    while (test--)
    {
        scanf("%d%d", &m, &n);
        for (int i=1; i<=n; ++i)
        {
            scanf("%d", &t[i][0]);
            for (int j=1; j<=t[i][0]; ++j) scanf("%d", &t[i][j]);
        }

        printf("%d\n", SanXuat(1, m));
    }

    return 0;
}