include<iostream>

include<cstdio>

include<cstring>

using namespace std; int main(){ int dp[33000],v[70][3],w[70][3],n,m; cin>>n>>m; int k=0; memset(v,0,sizeof(v)); for(int i=1;i<=m;i++){ int p,a,b; scanf("%d%d%d",&a,&b,&p); if (p==0){v[++k][0]=a;w[k][0]=b;} else if(v[p][1]==0) {v[p][1]=a;w[p][1]=b;} else {v[p][2]=a;w[p][2]=b;}; } memset(dp,-1,sizeof(dp)); dp[0]=0; for(int i=1;i<=k;i++){ for(int j=n-v[i][0];j>=0;j--){ if (dp[j]==-1)continue; dp[j+v[i][0]]=max(dp[j+v[i][0]],dp[j]+v[i][0]w[i][0]); if ((j+v[i][0]+v[i][1])<=n) dp[j+v[i][0]+v[i][1]]=max(dp[j+v[i][0]+v[i][1]],dp[j]+v[i][0]w[i][0]+v[i][1]w[i][1]); if ((j+v[i][0]+v[i][2])<=n) dp[j+v[i][0]+v[i][2]]=max(dp[j+v[i][0]+v[i][2]],dp[j]+v[i][0]w[i][0]+v[i][2]w[i][2]); if ((j+v[i][0]+v[i][1]+v[i][2])<=n) dp[j+v[i][0]+v[i][1]+v[i][2]]=max(dp[j+v[i][0]+v[i][1]+v[i][2]],dp[j]+v[i][0]w[i][0]+v[i][1]w[i][1]+v[i][2]w[i][2]); } //for(int j=1;j<=n;j++){ // if (dp[j]!=-1) cout<<j<<" "<<dp[j]<<";"; //} //cout<<endl; } int maxs=-1; for(int i=1;i<=n;i++)maxs=max(maxs,dp[i]); cout<<maxs; return 0; }