#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ffor(i,a,b) for(ll i=a;i<=b;i++)
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll s, n;
cin >> s >> n;
vector<ll> dp(s+1, 0);
ffor(it,1,n){
ll v, w, k;
cin >> v >> w >> k;
if(w == 0) continue;
ll maxCountNeeded = (s / w) + 1;
if(k >= maxCountNeeded){
ffor(j,w,s){
ll nv = dp[j-w] + v;
if(nv > dp[j]) dp[j] = nv;
}
continue;
}
vector<ll> prv = dp;
vector<ll> q_idx(s+1), q_val(s+1);
ll limr = min(w-1, s);
ffor(r,0,limr){
ll mmax = (s - r) / w;
if(mmax < 0) continue;
ll head = 0, tail = 0;
ffor(m,0,mmax){
ll j = r + m*w;
ll cand = prv[j] - m * v;
while(head < tail && q_val[tail-1] <= cand) --tail;
q_idx[tail] = m;
q_val[tail] = cand;
++tail;
while(head < tail && q_idx[head] < m - k) ++head;
ll best = q_val[head] + m * v;
if(best > dp[j]) dp[j] = best;
}
}
}
ll ans = 0;
ffor(i,0,s) if(dp[i] > ans) ans = dp[i];
cout << ans << '\n';
return 0;
}
