#include<bits/stdc++.h> using namespace std; using ll = long long; #define ffor(i,a,b) for(ll i=a;i<=b;i++) int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll s, n; cin >> s >> n; vector<ll> dp(s+1, 0); ffor(it,1,n){ ll v, w, k; cin >> v >> w >> k; if(w == 0) continue; ll maxCountNeeded = (s / w) + 1; if(k >= maxCountNeeded){ ffor(j,w,s){ ll nv = dp[j-w] + v; if(nv > dp[j]) dp[j] = nv; } continue; } vector<ll> prv = dp; vector<ll> q_idx(s+1), q_val(s+1); ll limr = min(w-1, s); ffor(r,0,limr){ ll mmax = (s - r) / w; if(mmax < 0) continue; ll head = 0, tail = 0; ffor(m,0,mmax){ ll j = r + m*w; ll cand = prv[j] - m * v; while(head < tail && q_val[tail-1] <= cand) --tail; q_idx[tail] = m; q_val[tail] = cand; ++tail; while(head < tail && q_idx[head] < m - k) ++head; ll best = q_val[head] + m * v; if(best > dp[j]) dp[j] = best; } } } ll ans = 0; ffor(i,0,s) if(dp[i] > ans) ans = dp[i]; cout << ans << '\n'; return 0; }