#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int v[100005],p[100005],q[100005],w[100005];
struct abc{
	int v,w;
}P[100005][4];

int f[100005];
int n,m,ans=-1;
void spe(){
	
	for(int i=1;i<=m;i++){
		    if(f[i]==i){
		    	P[f[i]][1].w=w[i];
			    P[f[i]][1].v=v[i];
		    }
			else {
				P[f[i]][++P[f[i]][0].v].v=v[i];
				P[f[i]][P[f[i]][0].v].w=w[i];
//				cout << P[f[i]][0].v << " ";
			}
		
	}
	
	return ;
}

int main(){	
    memset(v,0,sizeof(v));
    memset(p,0,sizeof(p));
    memset(q,0,sizeof(q));
    memset(w,0,sizeof(w));
	
	cin>>n>>m;	
    for(int i=1;i<=m;i++) P[i][0].v=1;
	for(int i=1;i<=m;++i){		
		cin>>v[i]>>p[i]>>f[i];
		if(f[i]==0) f[i]=i;	
		w[i]=p[i]*v[i];
	}
	
	spe();
	
	for(int i=1;i<=m;i++){
		for(int j=n;j>=0;j--){
			if(j-P[i] [1].v>=0){				
				f[j]=max(f[j],f[j-P[i][1].v]+P[i][1].w);
			}
			if(j-P[i][1].v-P[i][2].v>=0){
				f[j]=max(f[j],f[j-P[i][1].v-P[i][2].v]+P[i][1].w+P[i][2].w);
			}
			if(j-P[i][1].v-P[i][3].v>=0){
				f[j]=max(f[j],f[j-P[i][1].v-P[i][3].v]+P[i][1].w+P[i][3].w);
			}
			if(j-P[i][1].v-P[i][2].v-P[i][3].v>=0){
				f[j]=max(f[j],f[j-P[i][1].v-P[i][2].v-P[i][3].v]+P[i][1].w+P[i][2].w+P[i][3].w);
			}
//			cout << f[j] << " ";
//			ans=max(ans,f[j]);
		}
	}
	
	cout<<f[n];
	return 0;	
}