#include <bits/stdc++.h> using namespace std; #define ll long long int n,s; ll dp[105][2005], v[105], k[105]; int w[105]; ll dp_(int i, int wt){ if(i==0 || wt==0) return 0; if(dp[i][wt] != -1) return dp[i][wt]; ll nt = dp_(i-1, wt); ll t = 0; for(ll j=1;j<=min(k[i], (ll)wt/w[i]);++j) t = max(t, dp_(i-1, wt-j*w[i]) + j * v[i]); return dp[i][wt] = max(nt, t); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin>>s>>n; for(int i=1;i<=n;++i) cin>>v[i]>>w[i]>>k[i]; memset(dp,-1,sizeof(dp)); cout<<dp_(n,s); return 0; }