#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 dp[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;
int cnt=0;
for (int i=1;i<=n;i++){
int v,w,c;
cin>>v>>w>>c;
for (int r=0;r<w;r++){
deque<pair<ll,int>> dq;
for (int k=0;r+k*w<=s;k++){
int j=r+k*w;
ll val=dp[j]-1ll*k*v;
while (!dq.empty() && dq.back().first<=val) dq.pop_back();
dq.push_back({val,k});
while (!dq.empty() && dq.front().second<k-c) dq.pop_front();
dp[j]=dq.front().first+1ll*k*v;
}
}
}
cout<<dp[s];
return 0;
}
