#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) int main(){ FASTIO; int S; int N; if(!(cin>>S>>N)) return 0; vector<ll> dp(S+1, LLONG_MIN/4); dp[0]=0; for(int i=0;i<N;i++){ ll V; int W; long long K; cin>>V>>W>>K; if(W> S) continue; vector<ll> old = dp; for(int r=0;r<W;r++){ deque<int> dq; int maxm = (S - r) / W; for(int m=0;m<=maxm;m++){ int pos = m*W + r; ll val = old[pos] - m*V; while(!dq.empty()){ int j = dq.back(); ll vj = old[j*W + r] - j*V; if(vj <= val) dq.pop_back(); else break; } dq.push_back(m); while(!dq.empty() && m - dq.front() > K) dq.pop_front(); int j = dq.front(); dp[pos] = max(dp[pos], old[j*W + r] + (m - j) * V); } } } ll ans = 0; for(int i=0;i<=S;i++) if(dp[i]>ans) ans=dp[i]; cout<<ans<<"\n"; return 0; }