#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(i,1,n){ ll v, w, k; cin >> v >> w >> k; vector<ll> prv = dp; ffor(r,0,w-1){ if(r > s) break; ll mmax = (s - r) / w; vector<ll> q_idx(mmax+5), q_val(mmax+5); 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) ans = max(ans, dp[i]); cout << ans; return 0; }