11450

It’s a bottom up approach.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>

#define INF 100000000
using namespace std;

int MX;
vector<int> vb[21];
int dp[201][21];

void init()
{
	for(int i=0;i<21;i++)
	vb[i].clear();
	MX = INF;
	for(int i=0;i<201;i++)
		for(int j=0;j<21;j++)
		{
			if(j==0)
			dp[i][j]=0;
			else
			dp[i][j]=-1;//not solved
		}
}

int _max(int a,int b)
{
	if(a>b)
	return a;
	return b;
}
int main()
{
	int t,K,a;
	int M,C;
	scanf("%d",&t);
	while(t--)
	{
		init();
		scanf("%d%d",&M,&C);
		for(int i=1;i<=C;i++)
		{
			scanf("%d",&K);
			for(int j=0;j<K;j++)
			{
				scanf("%d",&a);
				vb[i].push_back(a);
			}
		}//for ends
		for(int i=1;i<=C;i++)
		{
			for(int j=0;j<vb[i].size();j++)
			{
				int val = vb[i][j];
				for(int k=0;k<=M;k++)
				{
					if(val<=k && dp[k-val][i-1]!=-1)
					dp[k][i]=_max(dp[k-val][i-1]+val,dp[k][i]);
				}
			}
		}
		if(dp[M][C]==-1)
		printf("no solution\n");
		else
		{
			printf("%d\n",dp[M][C]);
		}
	}
	return 0;
}