#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; vi v(n), w(n), k(n); for (int i = 0; i < n; ++i) { cin >> v[i] >> w[i] >> k[i]; } vector<ll> dp(s + 1); for (int i = 0; i < n; ++i) { for (int r= 0; r < w[i]; ++r) { queue<ll> q; int added = 0, removed = 0; for (int a = 0; a * w[i] + r <= s; ++a) { while (!q.empty() && q.front() < dp[a * w[i] + r] - v[i] * a) { q.pop(); removed++; } while (added - removed > k[i]) { q.pop(); removed++; } q.push({dp[a * w[i] + r] - v[i] * a}); added++; dp[a * w[i] + r] = q.front() + a * v[i]; } } } cout << dp[s] << '\n'; return 0; }