// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
#include <functional>
#include <utility>
using namespace std;
int main() {
int m,n; cin >> m >>n;
map<int,vector<pair<int,int>>> map;
for(int i=0; i<n; i++){
int v,w,k;cin>>v>>w>>k;
map[w].push_back(make_pair(v,k));
}
vector<int> prev(m+1);
for(auto i:map){
int w=i.first;
vector<int> curr(m+1);
for(int j=0; j<=m; j++)curr[j]=prev[j];
vector<pair<int,int>> pie=i.second;
sort(pie.begin(),pie.end(),greater<pair<int, int>>());
for(int j=0; j<=m; j++){
int k=0,p=pie[0].second-1,sum=pie[0].first,wait=w;
while(wait+j<=m){
curr[wait+j]=max(curr[wait+j],prev[j]+sum);
if(!p){
//cout<<p<<" "<<k<<endl;
k++;
// cout<<p<<" "<<k<<endl;
if(k>=pie.size())break;
p=pie[k].second;
}
sum+=pie[k].first;
wait+=w;
p--;
}
}
prev=curr;
}
int ans=0;
for(int j=0; j<=m; j++){
ans=max(ans,prev[j]);
}
cout<<ans;
}
