#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; }