/* http://www.magicoj.com/contest/problem?id=847&pid=2#problem-anchor */ #include<iostream> using namespace std; int m,n,a,b,c,w[1001][1001],v[1001][1001],mx; int dp[101][1001]; int main(){ cin >> m >> n; for(int i = 1;i <= n;i++){ cin >> a >> b >> c; w[c][++w[c][0]] = a; v[c][w[c][0]] = b; mx = max(mx,c); } for(int i = 1;i <= mx;i++){//分组遍历 for(int j = 1;j <= m;j++){//背包容量 dp[i][j] = dp[i-1][j]; for(int k = 1;k <= w[i][0];k++){//每组物品遍历 //cout << k << " "; if(j >= w[i][k]){ //cout << j << " " << w[i][k]<< endl; dp[i][j] = max(dp[i][j],dp[i-1][j-w[i][k]]+v[i][k]); } } } } cout << dp[mx][m]; return 0; }