#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,maxs=2000+10;
long long dp0[maxs],dp1[maxs],val[maxn],ted[maxn],n,s,pr[maxn];
void vorod(){
cin>>s>>n;
for(long long i=0;i<n;i++){
cin>>val[i]>>pr[i]>>ted[i];
}
}
void solve(){
for(long long i=0;i<n;i++){
for(long long j=0;j<pr[i];j++){
long long now=0;
deque<long long>dq;
//dq.push_back(0);
int f=1;
for(long long h=j;h<=s;h+=pr[i]){
if(f&&h!=0&&dp0[h]==0){
continue;
}
f=0;
dp0[h]-=now*val[i];
now++;
while((long long)dq.size()>0&&dq.back()<dp0[h]){
dq.pop_back();
}
dq.push_back(dp0[h]);
if(h-(ted[i]+1)*pr[i]>=0){
if(dq.front()==dp0[h-(ted[i]+1)*pr[i]]){
dq.pop_front();
}
}
dp1[h]=dq.front()+(now-1)*val[i];
}
}
for(long long j=0;j<=s;j++){
swap(dp1[j],dp0[j]);
if(i==n-1&&j>=1){
dp0[j]=max(dp0[j],dp0[j-1]);
}
dp1[j]=0;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
vorod();
solve();
cout<<dp0[s]<<endl;
}
