UVa 11450

this is an easy problem can be solved by dp...
state:
    dp[i][j] - whether can bought i garments with j units money
transition:
    dp[i][j]=dp[i-1][j+g[i][k]], for 0<=k<t[i] if dp[i-1][j]
    which means if we can buy i-1 garments with j units money then we can test all possibilities of garment i

/* UVas */
/*****************************************************************************/
int c, m, C, K;
int g[20][20];
int t[20];
int d[20][201];
int main(void) {
    cin>>c;
    while (c--) {
        cin>>m>>C;
        for (int i=0; i<C; i++) {
            cin>>t[i];
            for (int j=0; j<t[i]; j++) {
                cin>>g[i][j];
            }
        }
        memset(d, 0, sizeof(d));
        for (int i=0; i<t[0]; i++) {
            if (m-g[0][i]>=0) {
                d[0][g[0][i]]=1;
            }
        }
        for (int i=1; i<C; i++) {
            for (int j=0; j<=m; j++) {
                if (d[i-1][j]) {
                    for (int k=0; k<t[i]; k++) {
                        d[i][j+g[i][k]]=1;
                    }
                }
            }
        }
        int f=0;
        for (int i=m; i>=0; i--) {
            if (d[C-1][i]) {
                f=1;
                cout<<i<<endl;
                break;
            }
        }
        if (!f) {
            cout<<"no solution"<<endl;
        }
    }
    return 0;
}
/*****************************************************************************/