#include<bits/stdc++.h>
using namespace std;
long long int n,m,k,ans;
bool a[110][110];//第k件有无
long long int dp[10010],v[110][3],c[110][3];
//v[i][j] i主件j附件价格
//c[i][j] i主件j附件价值
int main(){
//	freopen("budget.in","r",stdin);
//	freopen("budget.out","w",stdout);
	cin>>m>>n;
	int x,y,q;
	for(int i=1;i<=n;i++){
		cin>>x>>y>>q;
		if(q>0){
			if(a[q][1]>0){
				a[q][2]=1;
				v[q][2]=x;
				c[q][2]=x*y;
			}
			else{
				a[q][1]=1;
				v[q][1]=x;
				c[q][1]=x*y;
			}
		}else{
			k++;
			a[k][0]=1;
			v[k][0]=x;
			c[k][0]=x*y;
		}
	}
	for(int i=1;i<=k;i++){
		for(int j=m;j>=1;j--){
		if(a[i][0]==1&&j>=v[i][0])
			dp[j]=max(dp[j],dp[j-v[i][0]]+c[i][0]);
		if(a[i][1]==1&&a[i][0]==1&&j>=v[i][1]+v[i][0])
			dp[j]=max(dp[j],dp[j-v[i][0]-v[i][1]]+c[i][0]+c[i][1]);
		if(a[i][2]==1&&a[i][0]==1&&j>=v[i][2]+v[i][0])
			dp[j]=max(dp[j],dp[j-v[i][0]-v[i][2]]+c[i][0]+c[i][2]);
		if(a[i][1]==1&&a[i][0]==1&&a[i][2]==1&&j>=v[i][2]+v[i][1]+v[i][0])
			dp[j]=max(dp[j],dp[j-v[i][2]-v[i][1]-v[i][0]]+c[i][2]+c[i][1]+c[i][0]);
		ans=max(ans,dp[j]);
		}
	}
	cout<<ans;



	fclose(stdin);fclose(stdout);
	return 0;
}