#include<bits/stdc++.h>
using namespace std;
const int N=3.2e4+5,M=65;
int n,m,v[M],p[M],q[M],s[M][M],dp[N],ans;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>v[i]>>p[i]>>q[i];
        s[q[i]][0]++;
        s[q[i]][s[q[i]][0]]=i;
    }
    for(int i=1;i<=m;i++)
        if(!q[i])
            for(int j=n;j>=v[i];j--){
                int tmp=max(dp[j],dp[j-v[i]]+v[i]*p[i]);
                if(j-v[i]-v[s[i][1]]-v[s[i][2]]>=0) tmp=max(tmp,dp[j-v[i]-v[s[i][1]]-v[s[i][2]]]+v[i]*p[i]+v[s[i][1]]*p[s[i][1]]+v[s[i][2]*p[s[i][2]]]);
                if(j-v[i]-v[s[i][1]]>=0)    tmp=max(tmp,dp[j-v[i]-v[s[i][1]]]+v[i]*p[i]+v[s[i][1]]*p[s[i][1]]);
                if(j-v[i]-v[s[i][2]]>=0)    tmp=max(tmp,dp[j-v[i]-v[s[i][2]]]+v[i]*p[i]+v[s[i][2]]*p[s[i][2]]);
                dp[j]=max(dp[j],tmp);
            }
    cout<<dp[n]<<"\n";
}