#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=70;
ll f[32010];
int s[N][3];
int v[N],w[N],b[N];
int val(int x){
    return w[x]*v[x];
}
int main(){
    int m; cin>>m;
    int n; cin>>n;
    for(int i=1,x;i<=n;i++){
        cin>>w[i]>>v[i]>>x;
        if(x) s[x][++s[x][0]]=i;
        else b[i]=1;
    }
    for(int i=1,s1,s2;i<=n;i++,s1=s2=0){
        if(!b[i]) continue;
        if(s[i][1]) s1=s[i][1];
        if(s[i][2]) s2=s[i][2];
        for(int j=m;j>=w[i];j--){
            if(j>=w[i])
                f[j]=max(f[j],f[j-w[i]]+val(i));
            if(s1&&j>=w[i]+w[s1])
                f[j]=max(f[j],f[j-w[i]-w[s1]]+val(i)+val(s1));
            if(s2&&j>=w[i]+w[s2])
                f[j]=max(f[j],f[j-w[i]-w[s2]]+val(i)+val(s2));
            if(s1&&s2&&j>=w[i]+w[s1]+w[s2])
                f[j]=max(f[j],f[j-w[i]-w[s1]-w[s2]]+val(i)+val(s1)+val(s2));
        }
    }
    cout<<f[m];
    return 0;
}

蒟蒻写码不易，求调。

附 $2$ 号数据：

输入

1000 5
300 5 0
400 2 0
300 5 2
300 4 2
600 4 0

输出

3900