#include <bits/stdc++.h> #include <climits> using namespace std; #define f first #define s second #define all(a) a.begin(),a.end() #define sz(a) (int)a.size() using ll=long long; struct info{ int v,w,k; }; const int N=1e5+5; info M[N]; int s,n; ll dp[2000+5]; void solve(){ cin>>s>>n; ll ans=0; for(int i=1;i<=n;++i) cin>>M[i].v>>M[i].w>>M[i].k; for(int i=1;i<=n;++i){ int remain=M[i].k; int maxlog=log2(M[i].k); for(int k=1;remain>0;k<<=1){ int take=min(k,remain); ll wei=(ll)M[i].w*take,val=(ll)M[i].v*take; remain-=take; if(wei>s) { break; } for(int j=s;j>=wei;--j){ dp[j]=max(dp[j],dp[j-wei]+val); ans=max(ans,dp[j]); } } } cout<<ans; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int T=1; while(T--) solve(); }