#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); while(n--) { int v, w, k; cin >> v >> w >> k; if(w > s) continue; for(int r = 0; r < w; r++) { deque<pair<int, int>> q; for(int i = 0, pos = r; pos <= s; i++, pos += w) { int base = dp[pos] -(int)i * v; while(!q.empty() and q.front().second < i - k) q.pop_front(); while(!q.empty() and q.back().first <= base) q.pop_back(); q.emplace_back(base, i); dp[pos] = q.front().first +(int)i * v; } } } cout << dp[s]; return 0; }