#include <bits/stdc++.h> using namespace std; #define int long long #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") void solve() { int n, x; cin >> x >> n; vector<int> price(n + 1), page(n + 1), num(n + 1); for (int i = 1; i <= n; i++) cin >> page[i] >> price[i] >> num[i]; vector dp(2, vector<int>(x + 1)); for (int i = 1; i <= n; i++) { for (int rem = 0; rem < price[i]; rem++) { deque<pair<int, int>> ms; auto add = [&] (int idx, int val) -> void { while (!ms.empty() && ms.back().second < val) ms.pop_back(); ms.emplace_back(idx, val); }; auto del = [&] (int idx) -> void { if (!ms.empty() && ms.front().first == idx) ms.pop_front(); }; auto maximum = [&] () -> int { return ms.front().second; }; for (int j = rem, cnt = 0; j <= x; j += price[i], cnt++) { add(j, dp[(i + 1) % 2][j] - cnt * page[i]); int outdatedIndex = j - (num[i] + 1) * price[i]; if (outdatedIndex >= 0) { del(outdatedIndex); } dp[i % 2][j] = maximum() + cnt * page[i]; } } } cout << dp[n % 2][x] << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int tc = 1; // cin >> tc; while (tc--) solve(); return 0; } // dp[i][j] = maximum number of pages i can buy having bought considering first i distinct books and with j money // dp[i][j] = dp[i - 1][j - (0..k[i]) * h[i]] + (0..k[i]) * s[i] // dp[i - 1][ j - (0...k[i]) * h[i] ] + (0...k[i]) * s[i]