#include<bits/stdc++.h>
using namespace std;
int num;
char ch;
int read()
{
	num=0;
	ch=getchar();
	while(ch<'0'||ch>'9')
	{
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		num=(num<<1)+(num<<3)+ch-'0';
		ch=getchar();
	}
	return num;
}
struct node{
	int weigth,val,with;
}a[1001];
int dp[1001];
bool cmp(node x,node y)
{
	return x.with<y.with;
}
int main()
{
	int n,m;
	m=read();
	n=read();
	for(int i=1;i<=n;++i)
	{
		a[i]=node{read(),read(),read()};
	}
	sort(a+1,a+n+1,cmp);
	a[0].with=-1;
	for(int i=1;i<=n;++i)
	{
		if(a[i].with==a[i-1].with)continue;
		for(int j=m;j>=0;--j)
		{
			for(int k=i;k<=n&&a[k].with==a[i].with;++k)
			{
				if(a[k].weigth>j)continue;
				dp[j]=max(dp[j],dp[j-a[i].weigth]+a[k].val);
			}
		}
	}
	printf("%d",dp[m]);
	return 0;
}