#include <algorithm>
#include <bits/stdc++.h>
#include <cctype>
using namespace std;
#define name "king2."
#define ll long long
#define vi vector<int>
const int N=1e7+5, mod=998244353, S=2005;
int n, s;
ll dp1[S], dp2[S];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen(name "in","r",stdin);
//freopen(name "out","w",stdout);
cin>>s>>n;
for (int i=1;i<=n;i++){
int v,w,c;
cin>>v>>w>>c;
if (w>s) continue;
swap(dp1,dp2);
for (int r=0;r<w;r++){
deque<int> dq;
for (int k=0;r+k*w<=s;k++){
int j=r+k*w;
ll val=dp1[j]-1ll*k*v;
while (!dq.empty()) {
int last = dq.back();
int pos = r + last * w;
if (dp1[pos] - (ll)last * v <= val)
dq.pop_back();
else break;
}
dq.push_back(k);
while (!dq.empty() && dq.front()<k-c) dq.pop_front();
int best=dq.front();
int pos=r+best*w;
dp2[j]=dp1[pos]+1ll*(k-best)*v;
}
}
}
cout<<dp2[s];
return 0;
}
