#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
// freopen("feast.in","r",stdin);
// freopen("feast.out","w",stdout);
int s,n;
cin>>s>>n;
vector<int> v(n),w(n),k(n);
for(int i=0; i<n; i++) cin>>v[i]>>w[i]>>k[i];
vector<vector<int>> dp(n+1,vector<int>(s+1,0));
int lol[s+1];
int st=1;
for(int i=0; i<n; i++){
st^=1;
memset(lol,0,sizeof(lol));
for(int j=w[i]; j<=s; j++){
if(dp[st][j-w[i]]+v[i]>dp[st][j] && lol[j-w[i]]<k[i]){
lol[j]=lol[j-w[i]]+1;
dp[st][j]=dp[st][j-w[i]]+v[i];
}
if(dp[st^1][j-w[i]]+v[i]>dp[st][j]){
lol[j]=1;
dp[st][j]=dp[st^1][j-w[i]]+v[i];
}
}
}
cout<<dp[st][s]<<'\n';
return 0;
}
