#include<iostream>
#define int long long
#define re register
#define zhuang_bi ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x7fffffff
using namespace std;

const int N = 1e7 + 5;

int m,n,k;
int cnt[N];
int a[N],b[N],c[N];
int dp[N];

signed main(){
	zhuang_bi;
	cin>>m>>n;
	for(re int i = 1;i <= n;i ++){
//		cout<<"还没炸×"<<i<<"\n";
		cin>>a[i]>>b[i]>>c[i];
		cnt[c[i]] ++;
		k = max(k,c[i]);
	}
//	cout<<"还没炸\n";
	for(re int i = 1;i <= n;i ++){
		for(re int v = m;v >= 0;v --){
			for(re int j = 1;j <= cnt[k];i ++){
				dp[v] = max(dp[v],dp[v - a[i]] + b[i]);
			}
		}
	}
	cout<<dp[m];
	return 0;
}