#include<iostream>
using namespace std;
const int maxn=3.2*1e4+5;
long long n,m;
struct node
{
	long long prc,w;
}a[maxn],g[maxn][3];
int cnt[maxn];
long long dp[maxn];

int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;++i)
	{
		long long prc,imp,q;
		cin>>prc>>imp>>q;
		if(q == 0)
		{
			a[i].prc=prc;
			a[i].w=prc*imp;
		}
		else
		{
			++cnt[i];
			g[i][cnt[i]].prc=prc;
			g[i][cnt[i]].w=prc*imp;
		}
	}
	for(long long i=1;i<=n;++i)
	{
		for(long long j=m;a[i].prc != 0 && j>=a[i].prc;--j)
		{
			dp[j]=max(dp[j],dp[j-a[i].prc]+a[i].w);
			if(j - a[i].prc - g[i][1].prc >= 0)
			{
				dp[j]=max(dp[j] , dp[j - a[i].prc - g[i][1].prc] + a[i].w + g[i][1].w);
			}
			if(j - a[i].prc - g[i][2].prc >= 0)
			{
				dp[j]=max(dp[j] , dp[j - a[i].prc - g[i][2].prc] + a[i].w + g[i][2].w);
			}
			if(j - a[i].prc - g[i][1].prc - g[i][2].prc >= 0)
			{
				dp[j]=max(dp[j] , dp[j - a[i].prc - g[i][1].prc - g[i][2].prc] + a[i].w + g[i][1].w + g[i][2].w);
			}
		}
	}
	cout<<dp[m];
	return 0;
}
/*
1000 5
800 2 0
400 5 1
300 5 1 
400 3 0
500 2 0
*/