#include <bits/stdc++.h>
using namespace std;
#define debug(v) cerr<<#v" = "<<(v)<<"\n";
#define debugvec(v) do{cerr<<#v<<" = [";for(int i=0;i<v.size();i++)cerr<<v[i]<<(i==v.size()-1?"":", ");cerr<<"]\n";}while(0);
#define debugvecp(v) do{cerr<<#v<<" = [";for(int i=0;i<v.size();i++)cerr<<"[ "<<v[i].fst<<" "<<v[i].snd<<" ]"<<(i==v.size()-1?"":", ");cerr<<"]\n";}while(0);
#define fst first
#define snd second
#define gcd(x,y) __gcd(x,y)
#define OnlineJudge(s) freopen((s".in"),"r",stdin); freopen((s".out"),"w",stdout);
#define fastIO() cin.tie(0)->sync_with_stdio(0);cin.exceptions(cin.failbit);
#define boolsolve() cout<<(solve()?"Yes":"No");
using ll=long long;
using ull=unsigned long long;
using pll=pair<ll,ll>;
using vll=vector<ll>;
using vpll=vector<pll>;
using vvll=vector<vll>;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll MAXN=601;
void solve(){
ll s, n, c=1, a, b;
cin >> s >> n;
map<ll,vpll> A;
for(int i=0; i<n; i++){
cin >> a >> b >> c;
if(b<=s) A[b].push_back({a,c});
}
c=1;
vvll dp(A.size()+1,vll(s+1,-INF)); dp[0][0]=0;
for(auto [w,B]:A){
sort(B.begin(),B.end(), greater<pll>());
for(int i=0; i<=s; i++){
dp[c][i]=dp[c-1][i];
ll cop=0, t=0, cur=0, bst=0;
while((cop+1)*w<=i && t<B.size()){
cop++; bst+=B[t].fst;
if(dp[c-1][i-cop*w]!=-INF) dp[c][i]=max(dp[c][i],dp[c-1][i-cop*w]+bst);
cur++;
if(cur==B[t].snd){
cur=0;
t++;
}
}
}
c++;
}
cout << *max_element(dp.back().begin(),dp.back().end());
}
int main(){
fastIO();
//OnlineJudge("snakes")
ll t=1;
//cin >> t;
while(t--){
solve();
//cout << "\n";
}
return 0;
}
