//UPDATERA ARRAY STORLEKEN!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF=1e15; const ll MAXS=2006;//UPDATERA ARRAY STORLEKEN!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 1e7 ll n,ans,s,k,v,w,dp[MAXS]; vector<ll> group[MAXS]; int main(){//多重背包模板 ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>s>>n; for(int i=1;i<=n;i++){ cin>>v>>w>>k; ll now=1; while(k>=now){ k-=now; if(w*now>s){ now*=2; continue;//k big, many unnecessary } group[w*now].push_back(v*now); now*=2; } if(k){ if(w*k>s) continue; group[w*k].push_back(v*k); } } for(int i=1;i<=s;i++) sort(group[i].begin(),group[i].end(),greater<ll>()); for(int i=1;i<=s;i++){ for(int j=0;j<group[i].size();j++){ for(int k=s;k>=i;k--){ dp[k]=max(dp[k],dp[k-i]+group[i][j]); ans=max(ans,dp[k]); } } } cout<<ans<<'\n'; }