#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include<string>

#define ll long long

#define INF 940000004

using namespace std;

ll v1[64],v2[64],v3[64],s1[64],s2[64],s3[64];

ll n,m,x,y,w;

ll maxn=0,f[32004]={0};

int main(){

cin>>m>>n;

for(int i=1;i<=n;i++){

cin>>x>>y>>w;

if(w!=0){

if(v2[w]==0){v2[w]=x;s2[w]=y;}

else{v3[w]=x;s3[w]=y;}

}else{

v1[i]=x;

s1[i]=y;

}

}

for(int i=1;i<=n;i++){

for(int j=m;j>=v1[i];j--){

f[j]=max(f[j],f[j-v1[i]]+v1[i]*s1[i]);

if(j-v1[i]-v2[i]>=0)

f[j]=max(f[j],f[j-v1[i]-v2[i]]+v1[i]*s1[i]+v2[i]*s2[i]);

if(j-v1[i]-v3[i]>=0)

f[j]=max(f[j],f[j-v1[i]-v3[i]]+v1[i]*s1[i]+v3[i]*s3[i]);

if(j-v1[i]-v2[i]-v3[i]>=0)

f[j]=max(f[j],f[j-v1[i]-v2[i]-v3[i]]+v1[i]*s1[i]+v2[i]*s2[i]+v3[i]*s3[i]);

maxn=max(maxn,f[j]);

}

}

cout<<maxn<<endl;

return 0;

}