#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ff first
#define ss second
#define m_p make_pair
#define INF LLONG_MAX
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
using vpii=vector<pii>;
int32_t main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int s,n;
cin>>s>>n;
vector<vpii> v(s+1);
while(n--){
int value,w,k;
cin>>value>>w>>k;
v[w].push_back({value,k});
}
vvi pref(s+1,vi(s+1,-1));
for(auto i=0;i<=s;i++) {
vpii c=v[i];
if(c.empty()) continue;
sort(c.begin(),c.end(),greater<pii>());
int it=0;
int sum=c[0].ss;
int ant=0;
while(sum<=s){
for(int j=ant;j<sum;j++) pref[i][j]=it;
int sz=c.size()-1;
if(it==sz) break;
it++;
ant=sum;
sum+=c[it].ss;
}
}
vi dp(s+1,-1);
dp[0]=0;
vector<pair<pair<int,int>,vi> > f(s+1,{{-1,-1},vi(s+1,0)});
f[0].ff={0,0};
for(int i=0;i<=s;i++){
if(dp[i]==-1) continue;
f[i].ss[f[i].ff.ss]=1;
for(int j=0;j<=s-i;j++){
if(v[j].empty()) continue;
f[i].ss[j]+=f[f[i].ff.ff].ss[j];
int it=pref[j][f[i].ss[j]];
if(it==-1) continue;
int s=i+j;
if(dp[s]<dp[i]+v[j][it].ff){
dp[s]=dp[i]+v[j][it].ff;
f[s].ff={i,j};
}
}
}
int ans=0;
for(auto i : dp) ans=max(ans,i);
cout<<ans<<endl;
return 0;
}
