#include<bits/stdc++.h>
#define N 1001
#define K 101
using namespace std;
struct thing{
	int a,b;
};
vector<thing> group[K];
int f[N],m,n,a,b,c,k=0;
//f[i]代表重量为i时的最大价值
//假设第c租有a1，a2，a3三件物品
//{f[i] f[i-a1]+b1 f[i-a2]+b2 f[i-a3]+b3}中选取最大的
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>a>>b>>c;
		group[c].push_back({a,b});
		//第c组中增加了一件重量为a，价值为b的物品
		for(int j=a;j>=a;j--){
			f[j]=max(f[j],f[j-a]+b);
}
		k=max(k,c);//把最大组编号记录下来
	}
	cout<<f[m];
	
    return 0;
}