#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int S, N; if (!(cin >> S >> N)) return 0; vector<ll> dp(S + 1, 0); for (int i = 0; i < N; ++i) { ll v, k; int w; cin >> v >> w >> k; if (w > S) continue; // không nhét nổi 1 cái ll maxCnt = min(k, (ll)S / w); if (maxCnt <= 0) continue; // 1) Nếu k*w >= S: coi như unbounded knapsack if (maxCnt * w >= S) { for (int cap = w; cap <= S; ++cap) { dp[cap] = max(dp[cap], dp[cap - w] + v); } } else { // 2) Bounded với k nhỏ: dùng monotone queue vector<ll> old = dp; // dp_old for (int r = 0; r < w; ++r) { deque<pair<int,ll>> dq; // {index j, value f(j)} int j = 0; for (int pos = r; pos <= S; pos += w, ++j) { ll cur = old[pos] - 1LL * j * v; // thêm f(j) vào deque, giữ giảm dần theo value while (!dq.empty() && dq.back().second <= cur) dq.pop_back(); dq.emplace_back(j, cur); // cửa sổ chỉ giữ j' >= j - maxCnt while (!dq.empty() && dq.front().first < j - (int)maxCnt) dq.pop_front(); dp[pos] = dq.front().second + 1LL * j * v; } } } } cout << dp[S] << '\n'; return 0; }