#include <bits/stdc++.h>
#define scan(a, __n) for(int __ = 0; __ < __n; __++)cin >> a[__];
// #define print(a, __n) for(int ___ = 0; ___ < __n; ___++)cout << a[___] << ' '; cout << '\n';
#define int ll
#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
// #define fr first
// #define sc second
#define all(v) v.begin(), v.end()
// #define c0 (v<<1)
// #define c1 (c0|1)
// #define md ((l+r)/2)
typedef long long ll;
typedef double ld;
using namespace std;
const int mod = 1e9+7;
const int maxN = 2007;
// const int maxFac = maxN;
// ll fac[maxFac], _fac[maxFac];
// ll po(ll b, ll p){
// b %= mod;
// p %= mod-1;
// ll r = 1;
// while(p){
// if(p&1)r = r*b%mod;
// p >>= 1;
// b = b*b%mod;
// }
// return r;
// }
// ll choose(ll k, ll n){
// return fac[n]*_fac[k]%mod*_fac[n-k]%mod;
// }
// ll factorial(ll n, ll k){
// ll ret = 1;
// for(ll i = n; i >= n-k+1; i--){
// ret = ret*i%mod;
// }
// return ret;
// }
int dp[maxN];
deque<pair<int, int>> dq[maxN];
int v, w, k;
void add(int val, int i, int ind){
while(dq[ind].size() > 0 && dq[ind].front().second <= val){
// if(ind == 0)cout << "rem1 " << dq[0].front().first << '\n';
dq[ind].pop_front();
}
dq[ind].push_front({i, val});
// if(ind == 0)cout << "add " << dq[0].front().first << '\n';
}
void rem(int i){
int ind = i % w;
if(dq[ind].back().first <= i){
// if(ind == 0)cout << "rem2 " << dq[0].back().first << '\n';
dq[ind].pop_back();
}
}
void slv(){
int s, n;
cin >> s >> n;
for(int i = 0; i < n; i++){
cin >> v >> w >> k;
int lazy[s] = {0};
for(int i = 0, ind = 0; i <= s; i++, ind++){
if(ind >= w)ind -= w;
lazy[ind] += v;
add(dp[i]-lazy[ind], i, ind);
if(i >= w*1ll*k+w){
rem(i-w*k-w);
}
dp[i] = dq[ind].back().second+lazy[ind];
}
for(int i = 0; i < s; i++){
// cout << dp[i] << ' ';
}
// cout << endl;
for(int i = 0; i < w; i++)dq[i].clear();
}
cout << dp[s] << endl;
}
signed main(){
// freopen("time.in", "r", stdin);
// freopen("time.out", "w", stdout);
// fastIO;
// cout << fixed << setprecision (15);
// fac[0] = 1;
// for(int i = 1; i < maxFac; i++)fac[i] = fac[i-1]*i%mod;
// _fac[maxFac-1] = po(fac[maxFac-1], mod-2);
// for(int i = maxFac-2; i >= 0; i--)_fac[i] = _fac[i+1]*(i+1)%mod;
// w[0] = 1;
// for(int i = 1; i < maxN; i++)w[i] = w[i-1]*p%mod;
// _w[maxN-1] = po(w[maxN-1], mod-2);
// for(int i = maxN-2; i >= 0; i--)_w[i] = _w[i+1]*p%mod;
int t = 1;
// cin >> t;
while(t--){
// cout << "**S" << endl;
// cout << slv() << '\n';
slv();
// string s;
// cin >> s;
// bool x = slv();
// cout << (x?"YES":"NO") << '\n';
}
}
/*
*/
