#include <bits/stdc++.h>
#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
#define forn(i,a,b) for(int i = a; i<b; i++)
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const int MAXM = 2000+5;
ll n,s;
ll dp[MAXM][MAXM];
vector<ll> p[MAXM];
ll f(ll x, ll y){
ll &res = dp[x][y];
if(res!=-1) return res;
if(x>s) return (ll)-10000000000;
if(y+x>s) return (ll)0;
res=f(x,y+1);
ll gain = 0;
forn(i,0,SZ(p[y])){
if(x+(y*(i+1))>s) break;
gain+=p[y][i];
res=max(res,f(x+(y*(i+1)),y+1)+gain);
}
//if(y==15) cout<<x<<" "<<res<<" "<<SZ(p[y])<<'\n';
return res;
}
int main(){
cin>>s>>n;
vector<pair<double,ll>> best(n);
vector<pair<ll,ll>> ww[s+5];
forn(i,0,n){
ll v,w;
ll k; cin>>v>>w>>k;
ww[w].pb({v,k});
}
forn(i,0,s+5){
sort(ALL(ww[i]));
reverse(ALL(ww[i]));
forn(j,0,SZ(ww[i])){
forn(h,0,ww[i][j].snd){
p[i].pb(ww[i][j].fst);
if(SZ(p[i])*i>s) break;
}
if(SZ(p[i])*i>s) break;
}
}
mset(dp,-1);
cout<<f(0,1)<<'\n';
return 0;
}
