#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define pb push_back
#define vc vector
#define nn int n; cin>>n
#define mm int m; cin>>m
#define kk int k; cin>>k
using namespace std;
int mod=1e9+7;
int N=2*1e5+1;
void ai(vector<int> &v){
for(int i=1;i<v.size();i++){cin>>v[i];}
}
void solve(){
int S,N;
cin>>S>>N;
vector<vector<pair<int,int>>> witem(S+1);
for(int i=1;i<=N;i++){
int v,w,k;
cin>>v>>w>>k;
witem[w].pb({v,k});
}
for(int i=1;i<=S;i++){
sort(witem[i].begin(),witem[i].end(),[](pair<int,int> x,pair<int,int> y){
return x.first>y.first;
});
}
vector<pair<int,int>> item;
for(int i=1;i<=S;i++){
int t=0;
int j=0;
while(t<=S&&j<witem[i].size()){
int v=witem[i][j].first;
int k=witem[i][j].second;
while(k--&&t<=S){
t+=i;
item.pb({v,i});
}
j++;
}
}
vector<int> dp(S+1,0);
for(int i=0;i<item.size();i++){
int v=item[i].first;
int w=item[i].second;
for(int j=S;j>=0;j--){
if(j+w<=S){
dp[j+w]=max(dp[j+w],dp[j]+v);
}
}
}
cout<<dp[S]<<endl;
}
signed main(){
/*-#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
//freopen("superbull.in", "r", stdin);
//freopen("superbull.out", "w", stdout);
#endif*/
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1; //cin>>t;
while(t--){
solve();
}
}
