除了HACK全没过（

样例可过

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,m;
int im_w[N],im_c[N],sm_w[N][3],sm_c[N][3];
int dp[N];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		{
            int u,v,w;
            cin>>u>>v>>w;
            if(!w)
            {
                im_w[i]=u;
                im_c[i]=u*v;
            }
            else 
            {
                sm_w[w][0]++;
                sm_w[w][sm_w[w][0]]=u;
                sm_c[w][sm_w[w][0]]=u*v;
            }
        }
	for(int i=1;i<=m;i++)
        for(int j=n;im_w[i]!=0 && j>=im_w[i];--j)
        {
            dp[j]=max(dp[j],dp[j-im_w[i]+im_c[i]]);
            if(j>=im_w[i]+sm_w[i][1])
                dp[j]=max(dp[j],dp[j-im_w[i]-sm_w[i][1]]+im_c[i]+sm_c[i][1]);
            if(j>=im_w[i]+sm_w[i][2])
                dp[j]=max(dp[j],dp[j-im_w[i]-sm_w[i][2]]+im_c[i]+sm_c[i][2]);
            if(j>=im_w[i]+sm_w[i][1]+sm_w[i][2])
                dp[j]=max(dp[j],dp[j-im_w[i]-sm_w[i][1]-sm_w[i][2]]+im_c[i]+sm_c[i][1]+sm_c[i][2]);
        }
        cout<<dp[n];
}

rt