#include "bits/stdc++.h"
using namespace std;
//cycle edges = total edges-bridge edges
// adding cycle edges does not decrease the number of disconnected component but bridge edges do
// decreasing order of weight of edges . adding using dsu -> edges whoes parent already in the component is the cycle edges->can be found the min. weight prsent in cycle
const int md=1e9+7;
int main()
{
int s,n;
cin>>s>>n;
map<int,vector<pair<int,int > > > mp;
for(int i=1;i<=n;i++){
int vl,we,no;
cin>>vl>>we>>no;
if(we<=s && no>0){
mp[we].push_back(make_pair(vl,no));
}
}
vector<vector<int> > dp(mp.size()+1,vector<int>(s+1,0));
int st=1;
for(auto [w, items]:mp){
sort(items.begin(),items.end(),greater<pair<int,int> >());
for(int i=0;i<=s;i++){
dp[st][i]=dp[st-1][i];
int taken=0;
int subcls=0;
int curr_taken=0;
int addi=0;
while((taken+1)*w<=i && subcls<items.size()){
taken++;
addi+=items[subcls].first;
dp[st][i]=max(dp[st][i],dp[st-1][i-taken*w]+addi);
curr_taken++;
if(curr_taken==items[subcls].second){
curr_taken=0;
subcls++;
}
}
}
st++;
}
int maxv=0;
for(int i=0;i<=mp.size();i++){
maxv=max(maxv,dp[i][s]);
}
cout<<maxv<<endl;
return 0;
}
