#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int S,N; cin>>S>>N; static long long dp[2001]; for(int i=0;i<=S;i++) { dp[i] = -LLONG_MAX; } dp[0] = 0; for(int i=1;i<=N;i++) { long long V,W,K; cin>>V>>W>>K; for(int r=0;r<W;r++) { deque<int>q; for(int s=r;s<=S;s+=W) { long long cur = dp[s] - (s-r)/W * V; while(!q.empty() && (s - q.front())/W > K) { q.pop_front(); } while(!q.empty() && dp[q.back()] - (q.back()-r)/W * V <= cur) { q.pop_back(); } q.push_back(s); dp[s] = dp[q.front()] + (s - q.front())/W * V; } } } long long ans=0; for(int i=0;i<=S;i++) { ans = max(ans, dp[i]); } cout<<ans; return 0; }