#include <bits/stdc++.h> using namespace std; using ll = long long; const ll NEG = LLONG_MIN / 4; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int S, N; if (!(cin >> S >> N)) return 0; vector<ll> dp(S + 1, NEG); dp[0] = 0; for (int i = 0; i < N; ++i) { int v, w, c; cin >> v >> w >> c; // If unlimited (or enough copies to treat as complete knapsack) if ((long long)w * c >= S) { for (int j = w; j <= S; ++j) { if (dp[j - w] != NEG) dp[j] = max(dp[j], dp[j - w] + v); } continue; } // Bounded case: process by residues modulo w for (int r = 0; r < w; ++r) { // collect original values for indices idx = r + k*w int maxk = (S - r) / w; if (maxk < 0) continue; vector<ll> vals(maxk + 1); for (int k = 0; k <= maxk; ++k) { vals[k] = dp[r + k * w]; // original value for this residue } deque<int> q; // store k indices for (int k = 0; k <= maxk; ++k) { ll cur = vals[k] - (ll)k * v; // value used for queue comparisons while (!q.empty() && (vals[q.back()] - (ll)q.back() * v) <= cur) q.pop_back(); q.push_back(k); // drop too-old elements (more than c copies) while (!q.empty() && q.front() < k - c) q.pop_front(); int best = q.front(); if (vals[best] != NEG) { // candidate = vals[best] + (k - best) * v dp[r + k * w] = max(dp[r + k * w], vals[best] + (ll)(k - best) * v); } } } } // if dp[S] may be NEG meaning unreachable, you might want to print something else cout << (dp[S] == NEG ? 0LL : dp[S]) << '\n'; return 0; }