#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ss second
#define ff first
#define pb push_back
const ll mxs=2e3;
ll n,m,v,w,t,dp[mxs+5];
vector<pair<ll,ll>>wi[mxs+5];
bool cmp(pair<ll,ll>x,pair<ll,ll>y){return x.ff>y.ff;}
vector<ll>val[mxs+5];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
while(n--) {
cin>>v>>w>>t;
wi[w].pb({v,t});
}
for(ll i=1;i<=m;i++)
if(wi[i].size()) sort(wi[i].begin(),wi[i].end(),cmp);
for(ll i=1;i<=m;i++) {
ll j=0;
bool ck=0;
for(auto tmp:wi[i]){
if(ck) break;
v=tmp.ff;t=tmp.ss;
for(ll k=j+1; k<=j+t; k++) {
if(k*i>m) {break;ck=1;}
val[i].pb(v);
}
j+=t;
}
}
for(ll i=1;i<=m;i++) {
for(ll s=m;s>=0;s--) {
ll sum=0,cnt=0;
for(ll v:val[i]){
sum+=v; cnt++;
if(s>=cnt*i) dp[s]=max(dp[s],dp[s-cnt*i]+sum);
}
}
}
cout<<dp[m]<<"\n";
}
