#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; struct trip { ll w,v,a; }; vector <trip> vec; void solve() { cin >> M >> n; for(ll i=1; i<=n; ++i) { ll w,v,a; cin >> v >> w >> a; ll pw = 1; while(a > 0) { ll take = min(pw,a); vec.pb({w*take, v*take, 1}); a -= take; pw *=2; } } vector <ll> dp(M+1, 0); for(auto j:vec) { // cout << j.w << " " << j.v << " " << j.a << "\n"; for(ll i=M; i>=j.w; --i) dp[i] = max(dp[i - j.w] + j.v, dp[i]); } 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; }