#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define endl "\n"
#define ii pair<ll,ll>
#define pi pair<ll,ll>
#define pii pair<ll, pair<ll,ll> >
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define all(s) s.begin(), s.end()
#define szz(s) int(s.size())
using namespace std;
#define ve vector<ll>
const string NAME = "file";
const int M = 1e9+7;
const int N = 2e6;
bool cmp(ii a , ii b){
return a.fi > b.fi ;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n , k ;
cin >> k >> n ;
vector<vector<ii>>weight(k+5);
FOR(i,1,n){
ll x , y , c ;
cin >> x >> y >> c;
if(y<=k){
weight[y].pb({x,c}) ;
}
}
vector<ve>dp(k+5,ve(k+5,-1e18));
dp[0][0] = 0 ;
FOR(i,1,k){
// if(weight[i].size() == 0)continue ;
sort(all(weight[i]),cmp);
int tt = k/i ;
// if(weight[i].size() != 0 )
// cout<<tt<<" "<<endl;
vector<ll>cur ;
ll pos = 0 , cnt =0 ;
while(true){
if(cnt>=tt)break;
if(weight[i].size() <=pos)break;
if(weight[i][pos].se+cnt>=tt){
ll pk =tt- cnt;
for(ll xx = 1 ; xx <= pk ; xx++)cur.pb({weight[i][pos].fi});
break ;
}
ll pk = weight[i][pos].se;
cnt+=weight[i][pos].se;
for(ll xx = 1 ; xx <= pk ; xx++)cur.pb({weight[i][pos].fi});
pos++;
}
REP(t,k,0){
dp[i][t] = max(dp[i][t],dp[i-1][t]);
cnt =0 ;
for(ll j = 0 ; j < cur.size() ; j++){
// cout<<cur[j]<<endl;
cnt+=cur[j];
if(t-(j+1)*i>=0)
dp[i][t] = max(dp[i][t] , dp[i-1][t-(j+1)*i]+cnt) ;
}
}
}
ll res = 0 ;
FOR(i,0,k){
res=max(res,dp[k][i]);
}
cout<<res<<endl;
return 0 ;
}
