#include<iostream>
#include<algorithm>
#include <cstring>
using namespace std;
const int N = 1e5;
int Main_It[10000];

int F_It[10000][3];
int Mv[N];
int F_V[N][3];//附件价值
int f[N];
int value,mater,q;
int main(){
	int n,m;
	cin>>n>>m;


	for(int i=1;i<=m;i++){
	
		cin>>value>>mater>>q;
	
		if(!q){
			
			Main_It[i]=value;
			Mv[i]=mater*value;
		}
		else {
			F_It[q][0]++;
			F_It[q][F_It[q][0]]=value;
			F_V[q][F_It[q][0]]=mater*value;
		}
		
	}
	
	
	
	for(int i = 1; i <= m;i++){
		for(int j=n;Main_It[i]!=0&&j>=Main_It[i];j--){
			//1 只有主件
			f[j]=max(f[j],f[j-Main_It[i]]+Mv[i]);
			//2 主件＋附件1
			if(  j  >=Mv[i]+F_It[i][1]  ) 
				f[j]=max (f[j] , f[j - Main_It[i] - F_It[i][1]] +  Mv[i] +  F_V[i][1] );
			//3 主件+附件2 
			if(  j >=Mv[i]+F_It[i][2] ) 
				f[j]=max (f[j] , f[j - Main_It[i] - F_It[i][2]] +  Mv[i] +  F_V[i][2] );
			//4 主件＋附件1+附件2
			if(  j  >=Mv[i]+ F_It[i][1]+F_It[i][2]  ) 
				f[j]=max (f[j], f[j-Main_It[i] - F_It[i][1]- F_It[i][2]] + Mv[i] +  F_V[i][1] +  F_V[i][2] );
		}
	}
	cout<<f[n];
	return 0;
}