#include<bits/stdc++.h> using namespace std; #define int long long signed main() { int W,n,sum,i,j,msb; cin>>W>>n; vector<int> v(n),w(n),k(n),dp(W+1,0); vector<vector<int>> a(W+1); for(int i=0;i<n;i++) { cin>>v[i]>>w[i]>>k[i]; msb=31;j=0; sum=0; while(!((k[i]>>msb)&1)) msb--; while(j<msb) { if(w[i]*(1LL<<j)<=W) a[w[i]*(1LL<<j)].emplace_back(v[i]*(1LL<<j)); sum+=(1LL<<j); j++; } if(k[i]-sum>0 && w[i]*(k[i]-sum)<=W) a[w[i]*(k[i]-sum)].emplace_back(v[i]*(k[i]-sum)); } for(int i=1;i<=W;i++) { sort(a[i].begin(),a[i].end()); reverse(a[i].begin(),a[i].end()); for(int ww=W;ww>=1;ww--) { sum = 0; for(int j=0;j<a[i].size()&&i*(j+1)<=ww;j++) { sum+=a[i][j]; dp[ww] = max(dp[ww],dp[ww-i*(j+1)]+sum); } } } int ans=0; for(auto&x:dp) ans = max(ans,x); cout<<ans; return 0; }