#include <bits/stdc++.h> #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define F first #define S second #define pb push_back using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const ll MAX = 1e6+7; const ll MOD = 1e9+7; ll n,M; vector <ll> vec[2001]; void solve() { cin >> M >> n; for(ll i=1; i<=n; ++i) { ll w,v,a; cin >> v >> w >> a; a = min(a, M/w); ll pw = 1; while(a > 0) { ll take = min(pw,a); vec[w*take].pb(v*take); a -= take; pw *=2; } } vector <ll> dp(M+1, 0); for(ll i=1; i<=M; ++i) { for(ll j=0; j<min((ll)vec[i].size(), M/i); ++j) { for(ll k=M; k>=i; k--) dp[k] = max(dp[k-i] + vec[i][j], dp[k]); } } cout << dp[M]; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //if(fopen("TASK.INP","r")) { // freopen("TASK.INP","r",stdin); // freopen("TASK.OUT","w",stdout); //} solve(); cerr << "\n" << "Time elapsed: " << TIME << "s\n"; return 0; }