#include <bits/stdc++.h> using namespace std; #define int long long int s,n; struct item{ int v,w,k; item():v(0),w(0),k(0) {} item(int V,int W,int K):v(V),w(W),k(K) {} }; vector<item> items(100001); int dp[2001]; signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>s>>n; for(int i=1;i<=n;i++){ int v,w,k; cin>>v>>w>>k; items[i]=item(v,w,k); } for(int i=1;i<=n;i++){ int v=items[i].v, w=items[i].w, k=items[i].k; for(int j=2000;j>=w;j--){ //weight for(int p=1;p<=k;p++){ //number of copies if(j-p*w==0) dp[p*w]=max(dp[p*w],p*v); else if(j-p*w>0) dp[j]=max(dp[j],dp[j-p*w]+p*v); } } } cout<<dp[s]; }