#include <bits/stdc++.h> using namespace std; #define ll long long #define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) static ll dp[2005]; static ll oldv[2005]; int main(){ FASTIO; int N, S; cin>>S>>N; for(int i=0;i<=S;i++) dp[i]=0; for(int it=0; it<N; ++it){ ll v; int w; long long k; cin>>v>>w>>k; if(w> S) continue; for(int i=0;i<=S;i++) oldv[i]=dp[i]; if((long long)w * k >= S){ for(int cap=w; cap<=S; ++cap){ ll cand = dp[cap-w] + v; if(cand > dp[cap]) dp[cap] = cand; } for(int cap=w; cap<=S; ++cap){ ll cand = dp[cap-w] + v; if(cand > dp[cap]) dp[cap] = cand; } } else { for(int r=0; r<w; ++r){ int len = (S - r) / w + 1; deque<pair<ll,int>> dq; for(int t=0; t<len; ++t){ int pos = r + t*w; ll val = oldv[pos] - (ll)t * v; while(!dq.empty() && dq.back().first <= val) dq.pop_back(); dq.emplace_back(val,t); while(!dq.empty() && t - dq.front().second > k) dq.pop_front(); ll best = dq.front().first + (ll)t * v; if(best > dp[pos]) dp[pos] = best; } } } } cout<<dp[S]<<"\n"; return 0; }