//#pragma GCC target ("avx2")
//#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define pb push_back
const int N = 1e6+100;
const int mod=1e9+7;
vector < pair < int, int > > g[2100];
//int lcm(int a, int b) { return a / (__gcd(a, b)) * b; }
//int binpow(int a,int b){if(!b)return 1; if(b&1)return a*binpow(a,b-1)%mod; int x=binpow(a,b/2); return x*x%mod;}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int s, n;
cin >> s >> n;
int c[n+1], w[n+1], k[n+1], dp[s+5]{};
vector < pair < int, int > > a;
for(int i=1;i<=n;i++){
cin >> c[i] >> w[i] >> k[i];
if(w[i]<=s) g[w[i]].pb({c[i], k[i]});
}
for(int i=1;i<=2000;i++){
sort(g[i].begin(), g[i].end());
reverse(g[i].begin(), g[i].end());
}
for(int i=1;i<=2000;i++){
int t=2000/i;
for(auto [v, col] : g[i]){
if(t>col){
t-=col;
while(col--){
a.pb({i, v});
}
}
else{
while(t--){
a.pb({i, v});
}
break;
}
}
}
for(int i=1;i<=s;i++) dp[i]=-1e18;
for(int i=0;i<a.size();i++){
for(int j=s-a[i].F;j>=0;j--){
dp[j+a[i].F]=max(dp[j+a[i].F], dp[j]+a[i].S);
}
}
int ans=-1e18;
for(int i=0;i<=s;i++) ans=max(ans, dp[i]);
cout << ans;
}
