#pragma GCC optimize("O5,unroll-loops,inline,omit-frame-pointer") #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=native,fma") #include<bits/stdc++.h> #define int long long #define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0) using namespace std; int n,m,dp[2005]; signed main(void){ exoworldgd; cin>>n>>m; for(int i=0,v,w,k;i<m;i++){ cin>>v>>w>>k; for(int p=1;p<=k;p<<=1){ for(int j=n;j>=w*p;j--)dp[j]=max(dp[j],dp[j-w*p]+v*p); k-=p; } if(k)for(int j=n;j>=w*k;j--)dp[j]=max(dp[j],dp[j-w*k]+v*k); } cout<<dp[n]; }