#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll INF = (1LL<<60);
// Maximum S is 2000, so each residue class queue needs at most ceil(2001/1)=2001 slots
// but in general ceil(S/1)=S+1 is enough.
static int qbuf[2001][2005];
static int ql[2001], qr[2001];
static int seen[2001], timer = 1;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
vector<ll> dp(S+1, -INF), next_dp;
dp[0] = 0;
for(int it=0; it<N; it++){
ll v,w,k;
cin >> v >> w >> k;
timer++; // mark all residue‐classes fresh
next_dp = dp;
// For each residue r = 0..w-1 we will maintain a sliding-window maximum
// in qbuf[r] as a circular buffer [ql[r], qr[r]).
for(int r=0; r<w; r++){
seen[r] = timer; // mark as initialized
ql[r] = qr[r] = 0;
}
// We unroll get_score(i,j)=dp[j]+((i-j)/w)*v as
// dp[j] + ((i - j)/w)*v = dp[j] + ((i-r)/w - (j-r)/w)*v
// with i%w = j%w = r => (i-j)/w = (i-r)/w - (j-r)/w. But simplest is:
// let t = (i-r)/w, then score = dp[j] + t*v where j = r + q*w.
// We just inline the original formula and rely on compiler to optimize.
for(int i=0; i<=S; i++){
int r = i % w;
// lazy init check
if(seen[r] != timer){
seen[r] = timer;
ql[r] = qr[r] = 0;
}
// pop front if out of window [i-k*w .. i]
int limit = i - int(k*w);
while(ql[r] < qr[r] && qbuf[r][ql[r]] < limit)
ql[r]++;
// compute current candidate index i
// now push i into back, maintaining monotonicity by score
// strictly inline get_score
auto score_i = dp[i];
// pop back while new score >= back's score
while(ql[r] < qr[r]){
int j = qbuf[r][qr[r]-1];
// (i-j)/w * v = ((i-j)/w)*v
ll score_j = dp[j] + ll((i - j)/w)*v;
ll s_i = dp[i] + ll((i - i)/w)*v; // = dp[i]
if(s_i >= score_j) qr[r]--;
else break;
}
qbuf[r][qr[r]++] = i;
// now front holds index j maximizing dp[j] + ((i-j)/w)*v
int j_best = qbuf[r][ql[r]];
ll best_score = dp[j_best] + ll((i - j_best)/w)*v;
next_dp[i] = max(next_dp[i], best_score);
}
dp.swap(next_dp);
}
ll ans = 0;
for(ll x: dp) if(x>ans) ans = x;
cout << ans << "\n";
return 0;
}
