#include<bits/stdc++.h>
using namespace std;
// JANGAN LUPA CEK PERLU LL NGGAK
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define miku ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int lim=2000;
int prefval[lim+1][lim+1];
vector<pii>w[lim+1];
int dp[lim+10];
signed main(){
miku
int s,n;cin>>s>>n;
for(int i=1;i<=n;i++){
int v,ww,k;cin>>v>>ww>>k;
w[ww].pb({v,k});
}
for(int i=1;i<=lim;i++)sort(w[i].begin(),w[i].end(),greater<pii>());
for(int j=1;j<=lim;j++){
//kita coba knapsack untuk tiap weigth
// kita cuman bisa pake segini kali
if(!w[j].size())continue;
for(int i=s;i>=1;i--){
int v=0,cnt=0,nw=0,las=0;
for(int k=1;k<=lim/j;k++){
if(w[j][nw].se<cnt+1){
if(nw+1<w[j].size()){
nw++;
cnt=0;
}
else break;
}
las+=w[j][nw].fi;
cnt++;
if(i-j*k<0) break;
dp[i]=max(dp[i],dp[i-j*k]+las);
}
}
// cout<<j<<endl;
}
cout<<dp[s];
}
