#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); const ll NEG_INF = -(1LL << 60); int S, N; if (!(cin >> S >> N)) return 0; struct Item { int v, w; long long k; }; vector<Item> items; items.reserve(N); for (int i = 0; i < N; ++i) { int v, w; long long k; cin >> v >> w >> k; if (w <= S && k > 0) items.push_back({v, w, k}); // else skip: weight too large to ever pick even one copy } // dp[pos] = best value achievable with total weight exactly pos vector<ll> dp(S + 1, NEG_INF); dp[0] = 0; // Process each item type with monotonic-queue optimization for (const auto &it : items) { int v = it.v; int w = it.w; long long k = it.k; // copy current dp to prev (reads are from prev; writes to dp) auto prev = dp; // process residues modulo w for (int r = 0; r < w; ++r) { // deque stores pairs (j_index, value = prev[pos] - j*v) deque<pair<int, ll>> dq; // iterate over positions pos = r + j * w // j = 0,1,2,... ; pos <= S int maxJ = (S - r) / w; for (int j = 0; j <= maxJ; ++j) { int pos = r + j * w; // candidate value for x = j (to be pushed) // val = prev[pos] - j * v (only meaningful if prev[pos] != NEG_INF) ll cand = NEG_INF; if (prev[pos] != NEG_INF) cand = prev[pos] - (ll)j * v; // push candidate j: maintain deque decreasing by value if (cand != NEG_INF) { while (!dq.empty() && dq.back().second <= cand) dq.pop_back(); dq.emplace_back(j, cand); } // pop front if it's outside window [j - k, j] while (!dq.empty() && dq.front().first < j - k) dq.pop_front(); // front of deque is best x for current j if (!dq.empty()) { ll best = dq.front().second + (ll)j * v; // take max: maybe we don't take any of this item type (prev[pos] // already in dp) dp[pos] = max(dp[pos], best); } // else no valid candidate -> dp[pos] remains as is (can't use this item // type to reach pos) } } } // answer: maximum dp[pos] for pos in [0..S] (weight ≤ S) ll ans = 0; for (int pos = 0; pos <= S; ++pos) if (dp[pos] > ans) ans = dp[pos]; cout << ans << '\n'; return 0; }