#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)
int main(){
FASTIO;
int S; int N;
if(!(cin>>S>>N)) return 0;
vector<ll> dp(S+1, LLONG_MIN/4);
dp[0]=0;
for(int i=0;i<N;i++){
ll V; int W; long long K;
cin>>V>>W>>K;
if(W> S) continue;
vector<ll> old = dp;
for(int r=0;r<W;r++){
deque<int> dq;
int maxm = (S - r) / W;
for(int m=0;m<=maxm;m++){
int pos = m*W + r;
ll val = old[pos] - m*V;
while(!dq.empty()){
int j = dq.back();
ll vj = old[j*W + r] - j*V;
if(vj <= val) dq.pop_back();
else break;
}
dq.push_back(m);
while(!dq.empty() && m - dq.front() > K) dq.pop_front();
int j = dq.front();
dp[pos] = max(dp[pos], old[j*W + r] + (m - j) * V);
}
}
}
ll ans = 0;
for(int i=0;i<=S;i++) if(dp[i]>ans) ans=dp[i];
cout<<ans<<"\n";
return 0;
}
