#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int maxn=1e5+5;
int n,S;
vector<pair<int,int>> W[maxn];
vector<int> weight,val;
ll dp[2005];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>S>>n;
for(int i=1;i<=n;i++){
int v,w,k;
cin>>v>>w>>k;
k=min(k,S/w);
W[w].push_back({v,k});
}
for(int i=1;i<=S;i++){
sort(W[i].begin(),W[i].end(),[](pair<int,int> a,pair<int,int> b){
return a.f>b.f;
});
int cnt=0;
for(int j=0;j<W[i].size();j++){
int v=W[i][j].f;
int k=W[i][j].s;
if(cnt*i>S) break;
for(int x=1;x<=k;x++){
if(cnt*i>S) break;
cnt++;
weight.push_back(i);
val.push_back(v);
}
}
}
for(int i=0;i<weight.size();i++){
for(int s=S;s>=0;s--){
if(s-weight[i]>=0) dp[s]=max(dp[s],dp[s-weight[i]]+val[i]);
}
}
ll ans=0;
for(int i=1;i<=S;i++) ans=max(ans,dp[i]);
cout<<ans;
}
