#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
ll s,n,v[100001],w[100001],k[100001],maxV=0,f[2001];
vector<pair<ll,ll>> a[2001];
int main(){
cin >>s>>n;
for(ll i=1;i<=n;i++) cin >>v[i]>>w[i]>>k[i],maxV=max(maxV,k[i]);
memset(f,0,sizeof(f));
for(ll i=1;i<=n;i++) a[w[i]].push_back({v[i],k[i]});
for(ll i=0;i<=s;i++){
if(a[i].size()==0) continue; ll pos=0;
sort(a[i].begin(),a[i].end(),greater<pair<ll,ll>>());
for(ll j=0;j*i<s;j++){
if(pos>=a[i].size()) break;
for(ll k=s;k>=i;k--) f[k]=max(f[k],f[k-i]+a[i][pos].fi);
a[i][pos].se--; if(a[i][pos].se==0) pos++;
}
}cout <<f[s];
}
