#include <bits/stdc++.h> #define int long long using namespace std; struct Cake { int v, k; }; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int s, n; cin >> s >> n; vector<vector<Cake>> a(s + 1); for(int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; if(w <= s) a[w].push_back({v, k}); } vector<pair<int, int>> pick; for(int w = 1; w <= s; w++) { if(a[w].empty()) continue; sort(a[w].begin(), a[w].end(), [](const Cake& x, const Cake& y) { return x.v > y.v; }); int cap = s / w; for(auto &ck : a[w]) { int t = min(ck.k, cap); if(t == 0) break; cap -= t; for(int b = 1; t > 0; b <<= 1) { int num = min(b, t); pick.push_back({num * ck.v, (int)(num * w)}); t -= num; } if(cap == 0) break; } } vector<int> dp(s + 1, 0); for(auto &it : pick) { int val = it.first; int wt = it.second; for(int j = s; j >= wt; j--) dp[j] = max(dp[j], dp[j - wt] + val); } cout << *max_element(dp.begin(), dp.end()); return 0; }