//UPDATERA ARRAY STORLEKEN!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF=1e15; const ll MAXN=10000006,MAXS=2006;//UPDATERA ARRAY STORLEKEN!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 1e7 ll n,ans,s,k,v,w,cnt,dp[MAXS]; struct node{ ll v,w; }lst[MAXN]; 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; now*=2; if(w*now>s) continue; lst[++cnt].v=v*now; lst[cnt].w=w*now; } if(k){ if(w*k>s) continue; lst[++cnt].v=v*k; lst[cnt].w=w*k; } } for(int i=1;i<=cnt;i++){ for(int j=s;j>=lst[i].w;j--){ dp[j]=max(dp[j],dp[j-lst[i].w]+lst[i].v); ans=max(ans,dp[j]); } } cout<<ans<<'\n'; }