#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); ll dp[2005], ndp[2005]; int main(){ FASTIO; ll S; int N; cin >> S >> N; for(int i=0;i<=S;i++) dp[i]=0; while(N--){ ll v,w,k; cin >> v >> w >> k; for(int r=0;r<w;r++){ deque<pair<ll,int>> dq; for(int t=0, pos=r; pos<=S; t++, pos+=w){ ll val = dp[pos] - t*v; while(!dq.empty() && dq.back().first <= val) dq.pop_back(); dq.push_back({val, t}); while(!dq.empty() && t - dq.front().second > k) dq.pop_front(); ndp[pos] = dq.front().first + t*v; } } for(int i=0;i<=S;i++) dp[i]=max(dp[i], ndp[i]); } cout << dp[S]; }