#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int,int>; #define FOR(i,a,b) for (int i=(a); i<=(b); ++i) #define FORD(i,a,b) for (int i=(a); i>=(b); --i) #define pb push_back const int INF = 1e9; const int MOD = 998244353; const ll MOD2 = 1e9 + 7; const ll LL_INF = 4e18; const int MAXN = 1e6 + 1; void solve() { int s, n; cin >> s >> n; // obj[w] = list of (value, count) items with this weight w vector<vector<pair<ll,ll>>> obj(s + 1); FOR(i,1,n) { ll v, w, k; cin >> v >> w >> k; if (w > s || k == 0) continue; // can't use these at all obj[w].push_back({v, k}); } vector<ll> dp(s + 1, 0); // For each weight, process all items of that weight FOR(w,1,s) { auto &items = obj[w]; if (items.empty()) continue; // Sort by value descending so we always use best-value items first sort(items.begin(), items.end(), [](const pair<ll,ll> &a, const pair<ll,ll> &b) { return a.first > b.first; }); int id = 0; // We can use weight w at most s / w times in total (capacity limit) for (int used = 0; used * w <= s; ++used) { if (id >= (int)items.size()) break; // no more items of this weight // Classic 0/1 knapsack transition for *one* copy of current item for (int cap = s; cap >= w; --cap) { dp[cap] = max(dp[cap], dp[cap - w] + items[id].first); } // Decrease remaining multiplicity; move to next item when exhausted if (--items[id].second == 0) ++id; } } // Problem version that AC'ed used dp[s] as answer: cout << dp[s] << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int TC = 1; // cin >> TC; while (TC--) solve(); return 0; }