#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll pul[2001];
vector<ll> qrup[2001];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int s1,n;
cin>>s1>>n;
for(int i=0;i<n;i++){
ll v1,w,k;
cin>>v1>>w>>k;
if(w<=s1) qrup[w].push_back(v1), qrup[w].push_back(k);
}
for(int w=1;w<=s1;w++){
if(qrup[w].empty()) continue;
vector<pair<ll,ll>> d;
for(int i=0;i<qrup[w].size();i+=2) d.push_back({qrup[w][i], qrup[w][i+1]});
sort(d.rbegin(),d.rend());
int limit=s1/w, say=0;
for(auto &p:d){
for(int t=0;t<p.second && say<limit;t++){
for(int j=s1;j>=w;j--) pul[j]=max(pul[j],pul[j-w]+p.first);
say++;
}
if(say>=limit) break;
}
}
cout<<pul[s1];
return 0;
}
