#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) { deque<pair<ll, int>> q; for (ll a = 0; a * w[i] + r <= s; ++a) { while (!q.empty() && a - q.front().second > k[i]) { q.pop_front(); } while (!q.empty() && q.back().first <= dp[(i + 1) & 1][a * w[i] + r] - v[i] * a) { q.pop_back(); } q.push_back({dp[(i + 1) & 1][a * w[i] + r] - v[i] * a, a}); dp[i & 1][a * w[i] + r] =q.front().first + a * v[i]; } } } cout << dp[(n + 1) & 1][s] << '\n'; return 0; }