18 22 100 44 100 2 Sample Output
400 
#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;int main(){	int n,m,t;	int pri[101],w[101],c[101],dp[101];	scanf("%d",&t);	while(t--)	{		int Max=0;		memset(dp,0,sizeof(dp));		scanf("%d %d",&n,&m);		for(int i=0;i<m;i++)		{			scanf("%d %d %d",&pri[i],&w[i],&c[i]);		}		for(int i=0;i<m;i++)			for(int j=n;j>=pri[i];j--)				for(int k=1;k<=c[i];k++)				{					if(j<k*pri[i])//背包剩余金額<袋數(shù)*單價						break;					dp[j]=max(dp[j],dp[j-k*pri[i]]+k*w[i]);					if(Max<dp[j])						Max=dp[j]; 				}		printf("%d",Max);	}	return 0;	}