#include<bits/stdc++.h>
using namespace std;
struct node{
	int w,val,w1,val1,w2,val2;
}a[605];
int main(){
	int n,m,dp[100][2005],maxn=0;
	cin>>n>>m;
	int num=0;
	for(int i=1;i<=m;i++)
	{
		int w,v,t;
		cin>>w>>v>>t;
		if(t==0)
		{
			num++;
			a[num].w=w;
			a[num].val=w*v;
		} else {
			if(a[num].w1==0)
			{
				a[num].w1=w;
				a[num].val1=w*v;
			} else {
				a[num].w2=w;
				a[num].val2=w*v;
			}
		}
	}
	for(int i=1;i<=num;i++)
	{
		for(int j=n;j>=1;j--)
		{
			if(j>=a[i].w)
			{
				dp[i][j]=max(dp[i][j],dp[i][j-a[i].w]+a[i].val);
			}
			if(j>=a[i].w+a[i].w1)
			{
				dp[i][j]=max(dp[i][j],dp[i][j-a[i].w-a[i].w1]+a[i].val+a[i].val1);
			}
			if(j>=a[i].w+a[i].w2)
			{
				dp[i][j]=max(dp[i][j],dp[i][j-a[i].w-a[i].w2]+a[i].val+a[i].val2);
			}
			if(j>=a[i].w+a[i].w1+a[i].w2)
			{
				dp[i][j]=max(dp[i][j],dp[i][j-a[i].w-a[i].w1-a[i].w2]+a[i].val+a[i].val1+a[i].val2);
			}
		}
	}
	cout<<dp[n][m];
	return 0;
}