#include<iostream>
#include<cstdio>
using namespace std;
int n,v,w[1010],c[1010],sum,d[1010],maxn=-0x7ffffff,a[1010],b[1010][1010];
int main()
{
	cin>>v>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>c[i]>>sum;
		maxn=max(maxn,sum);
		a[sum]++;
		b[sum][a[sum]]=i;
	}
	for(int i=1;i<=maxn;i++)
		for(int j=v;j>=0;j--)
			for(int k=1;k<=a[i];k++)
				if(j>=w[b[i][k]]) 
				d[j]=max(d[j],d[j-w[b[i][k]]+c[b[i][k]]]);
	cout<<d[v];
	return 0;
}