#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int s,n;
cin>>s>>n;
vector<tuple<int,int,int>> l(n);
for (int i=0;i<n;i++){
int v,w,k;
cin>>v>>w>>k;
l[i]={v,w,k};
}
vector<long long> dp(s+1,-1e15);
dp[0]=0;
for (auto [v,w,k]:l){
vector<long long> copy=dp;
for (int r=0;r<w;r++){
deque<int> dq;
//dq.push_back(0);
for (int i=0;r+i*w<=s;i++){
int pos=r+i*w;
while (!dq.empty() && pos - (r+dq.front()*w) > k*w) dq.pop_front();
if (!dq.empty()) copy[pos]=max(copy[pos],dp[r+dq.front()*w]+1ll*(i-dq.front())*v);
if (dp[pos]==-1e15) continue;
while (!dq.empty()){
int j=dq.back();
if (dp[r+j*w] - 1ll*j*v >= dp[pos] - 1ll*i*v) break;
dq.pop_back();
}
dq.push_back(i);
}
}
dp=copy;
}
long long ans=0;
for (int i=0;i<=s;i++) ans=max(ans,dp[i]);
cout<<ans<<"\n";
return 0;
}
