#include<bits/stdc++.h>
using namespace std;
int n,m,dp[40005],fuji[40005][4],fujizh[40005][4],zhuj[40005],zhujzh[40005],val,imp,bel;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>val>>imp>>bel;
		if(bel!=0){
			fuji[bel][0]++;
			fuji[bel][fuji[bel][0]]=val;
			fujizh[bel][fuji[bel][0]]=val*imp;
		}
		if(bel==0){
			zhuj[i]=val;
			zhujzh[i]=val*imp;
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=n;j>=zhuj[i]&&zhuj[i]!=0;j--){
			if(j>zhuj[i]+fuji[i][1]+fuji[i][2]){
				dp[j]=max(dp[j],dp[j-zhuj[i]-fuji[i][1]-fuji[i][2]]+zhujzh[i]+fujizh[i][1]+fujizh[i][2]);
			}
			if(j>zhuj[i]+fuji[i][1]){
				dp[j]=max(dp[j],dp[j-zhuj[i]-fuji[i][1]]+zhujzh[i]+fujizh[i][1]);
			}
			if(j>zhuj[i]+fuji[i][2]){
				dp[j]=max(dp[j],dp[j-zhuj[i]-fuji[i][2]]+zhujzh[i]+fujizh[i][2]);
			}
			dp[j]=max(dp[j],dp[j-zhuj[i]]+zhujzh[i]);
		}
	}
	cout<<dp[n];
}