#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];
int tmp[maxN];
vector<pair<int, int>> gp[maxN];
int s, n;
int cal[maxN][maxN];
void make(int ind){
auto& g = gp[ind];
sort(all(g));
reverse(all(g));
vector<int> w;
for(auto u : g){
if(w.size() >= s)break;
while(w.size() < s && u.second > 0)w.push_back(u.first), u.second--;
}
for(int i = 0; i < w.size(); i++){
cal[ind][i+1] = cal[ind][i]+w[i];
}
}
int calcSin(int po, int lq, int rq, int ind){
// if(ind == 15)cout << "po " << po << " | ";
rq = min(rq, po);
tmp[po] = dp[po];
int ii = -1;
for(int i = lq; i <= rq; i++){
if(tmp[po] < dp[i]+cal[ind][(po-i)/ind]){
tmp[po] = dp[i]+cal[ind][(po-i)/ind];
ii = i;
}
}
// if(ind == 15)cout << ii << endl;
return ii;
}
void calcTmp2(int l, int r, int lq, int rq, int ind){
// for(int i = l; i <= r; i++)calcSin(i, lq, rq, ind);
}
void calcTmp(int l, int r, int lq, int rq, int ind){
// for(int i = l; i <= r; i++)calcSin(i, lq, rq, ind);
rq = min(r, rq);
if(r < l)return;
if(l == r){
calcSin(l, lq, rq, ind);
return;
}
int md = (l+r)>>1;
int xx = calcSin(md, lq, rq, ind);
calcTmp(l, md-1, lq, xx, ind);
calcTmp(md+1, r, xx, rq, ind);
// l <= j
//c[l][j] = cal[i][j-l];
}
void slv(){
cin >> s >> n;
for(int i = 0, v, w, k; i < n; i++){
cin >> v >> w >> k;
k = min(k, 3000);
gp[w].push_back({v, k});
}
for(int i = 1; i <= s; i++){
make(i);
calcTmp(0, s, 0, s, i);
// cout << endl;
// cout << i << " :\n";
// for(int j = 0; j <= s; j++)cout << tmp[j] << ' ';
// cout << endl;
// calcTmp2(0, s, 0, s, i);
// for(int j = 0; j <= s; j++)cout << tmp[j] << ' ';
// cout << endl;
// cout << endl;
for(int j = 0; j <= s; j++)dp[j] = tmp[j];
}
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';
}
}
/*
*/
