#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,x,y,z,dp[100][40010];
struct node{
	ll c,v;
};
vector<node> a[40010];
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y>>z;
		if(z==0){
			a[i].push_back({x,x*y});
		}else a[z].push_back({x,x*y});
	}
	for(int i=1;i<=n;i++){
		ll x=a[i].size();
		if(x==0){
			for(int j=0;j<=m;j++) dp[i][j]=dp[i-1][j];
			continue;
		}
		for(int j=0;j<=m;j++){
			if(j<a[i][0].c){
				dp[i][j]=dp[i-1][j];
				continue;
			}
			if(x==1)
				dp[i][j]=max(dp[i][j],dp[i-1][j-a[i][0].c]+a[i][0].v);
			if(x==2){
				if(j>=a[i][0].c) dp[i][j]=max(dp[i][j],max(dp[i-1][j-a[i][0].c]+a[i][0].v,dp[i-1][j]));
				if(j>=a[i][0].c+a[i][1].c){
					dp[i][j]=max(dp[i][j],max(dp[i-1][j-a[i][0].c]+a[i][0].v,dp[i-1][j]));
					dp[i][j]=max(dp[i][j],dp[i-1][j-a[i][0].c-a[i][1].c]+a[i][0].v+a[i][1].v);
				}
			}if(x==3){
				if(j>=a[i][0].c) dp[i][j]=max(dp[i][j],max(dp[i-1][j-a[i][0].c]+a[i][0].v,dp[i-1][j]));
				if(j>=a[i][0].c+a[i][1].c){
					dp[i][j]=max(dp[i][j],max(dp[i-1][j-a[i][0].c]+a[i][0].v,dp[i-1][j]));
					dp[i][j]=max(dp[i][j],dp[i-1][j-a[i][0].c-a[i][1].c]+a[i][0].v+a[i][1].v);
				}if(j>=a[i][0].c+a[i][1].c+a[i][2].c){
					dp[i][j]=max(dp[i][j],max(dp[i-1][j-a[i][0].c]+a[i][0].v,dp[i-1][j]));
					dp[i][j]=max(dp[i][j],dp[i-1][j-a[i][0].c-a[i][1].c]+a[i][0].v+a[i][1].v);
					dp[i][j]=max(dp[i][j],dp[i-1][j-a[i][0].c-a[i][1].c-a[i][2].c]+a[i][0].v+a[i][1].v+a[i][2].v);
				}
			}
		}
	}
	cout<<dp[n][m];
	return 0;
}