#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int s,n;
cin>>s>>n;
vector<pair<int,int> >wei[s+1];
for(int q=1;q<=n;q++){
int v,w,k;
cin>>v>>w>>k;
wei[w].push_back({v,k});
}
vector<pair<int,int> >hmm;
for(int q=1;q<=s;q++){
sort(wei[q].rbegin(),wei[q].rend());
int idx=0;
int rts=wei[q].size();
for(int w=1;w<=s/q;w++){
if(idx==rts)break;
hmm.push_back({wei[q][idx].first,q});
wei[q][idx].second--;
if(wei[q][idx].second==0)idx++;
}
}
int dp[s+1];
for(int q=0;q<=s;q++)dp[q]=0;
for(auto r : hmm){
for(int wei=s;wei>=r.second;wei--){
dp[wei]=max(dp[wei],dp[wei-r.second]+r.first);
}
}
cout<<dp[s]<<endl;
}
