#include<bits/stdc++.h>
using namespace std;
int n,m;
int v[110],p[110],q[110];
vector<int>vp[110];
int dp[int(3.2e4)+10],f[int(3.2e4)+10];
int main() {
	cin>>m>>n;//m,n倒着的
	for(int i=1;i<=n;i++)
		cin>>v[i]>>p[i]>>q[i],vp[q[i]].push_back(i),p[i]*=v[i];//将附件搞进vector
	for(int i=1;i<=n;i++){
		if(q[i]!=0) continue;//附件跳过
		for(int j=0;j<=m;j++)//copy上一个状态
			f[j]=dp[j];
		for(int j=m;j>=v[i];j--)//只选这个
			dp[j]=max(f[j],f[j-v[i]]+p[i]);
		if(vp[i].size()==0) continue;//无附件，continue
		if(vp[i].size()>=1)//附件>=1个，只选第一个附件
			for(int j=m;j>=v[i]+v[vp[i][0]];j--)
				dp[j]=max(f[j],f[j-v[i]-v[vp[i][0]]]+p[i]+p[vp[i][0]]);
		if(vp[i].size()==1) continue; //接下来是有两个附件的主场
		for(int j=m;j>=v[i]+v[vp[i][1]];j--)//只选第二个附件
			dp[j]=max(f[j],f[j-v[i]-v[vp[i][1]]]+p[i]+p[vp[i][1]]);
		for(int j=m;j>=v[i]+v[vp[i][0]]+v[vp[i][1]];j--)//两个附件都选
			dp[j]=max(f[j],f[j-v[i]-v[vp[i][0]]-v[vp[i][1]]]+p[i]+p[vp[i][0]]+p[vp[i][1]]);
	}
	cout<<dp[m];
	return 0;
}