#include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using vi = vector<int>; #define all(x) (x).begin(), (x).end() int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); int s, n; cin >> s >> n; vector<ll> v(n), w(n), k(n); for (ll i = 0; i < n; ++i) { cin >> v[i] >> w[i] >> k[i]; } vector<vector<ll>> dp(2, vector<ll>(s + 1)); for (int i = 0; i < n; ++i) { for (ll r= 0; r < w[i]; ++r) { stack<pair<pair<ll, int>, ll>> st1, st2; for (ll a = 0; a * w[i] + r <= s; ++a) { if (st2.empty()) { while (!st1.empty()) { auto element = st1.top().first; st1.pop(); ll maximum = st2.empty() ? element.first : max(element.first, st2.top().second); st2.push({element, maximum}); } } while (!st2.empty() && a - st2.top().first.second > k[i]) { st2.pop(); } ll cur_val = dp[(i + 1) & 1][a * w[i] + r] - v[i] * a; ll maximum = st1.empty() ? cur_val : max(cur_val, st1.top().second); st1.push({{cur_val, a}, maximum}); if (!st2.empty()) maximum = max(maximum, st2.top().second); dp[i & 1][a * w[i] + r] = maximum + a * v[i]; } } } cout << dp[(n + 1) & 1][s] << '\n'; return 0; }