#include <bits/stdc++.h> #define int long long using namespace std; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int s, n; cin >> s >> n; vector<int> dp(s + 1, 0); for(int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; if(w > s) continue; for(int mod = 0; mod < w; mod++) { deque<pair<int, int>> dq; for(int j = 0; mod + j * w <= s; j++) { int x = mod + j * w; int cur = dp[x] - j * v; while(!dq.empty() and dq.back().first <= cur) { dq.pop_back(); } dq.push_back({cur, j}); if(dq.front().second < j - k) dq.pop_front(); dp[x] = dq.front().first + j * v; } } } cout<<dp[s]; return 0; }