#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;
}
