#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define ff first
#define ss second
#define pb(x) push_back(x)
#define vii vector<ll>
#define ump unordered_map
#define sz(a) (int)a.size()
#define getbit(i, j) ((i >> j) & 1)
#define addbit(i, j) (i | (1 << j))
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define fto(i, a, b, x) for (int i = a; i <= b; i += x)
#define fdto(i, a, b, x) for (int i = a; i >= b; i -= x)
#define all(x) x.begin(), x.end()
using namespace std;
const ll maxN = 1e5+5;
const ll INF = 1e18;
int S, n;
ll v[maxN], w[maxN], k[maxN];
vector<ll> g[2005];
vector<ii> b[2005];
vector<ll> f;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> S >> n;
fto (i, 1, n, 1) {
cin >> v[i] >> w[i] >> k[i];
}
// fto (i, 1, S, 1) fto (j, 1, S, 1) g[i][j] = -INF;
fto (i, 1, n, 1) {
b[w[i]].emplace_back(v[i], k[i]);
}
fto (i, 1, S, 1) sort(all(b[w[i]]), greater<ii>());
fto (i, 1, S, 1) {
if (!b[i].size()) continue;
int total = 0;
int j = 0;
g[i].emplace_back(0);
fto (t, i, S, i) {
if (total == b[i][j].ss) j++, total = 0;
if (j == b[i].size()) break;
total++;
g[i].emplace_back(g[i].back() + b[i][j].ff);
}
}
f.assign(S+2, -INF);
f[0] = 0;
fto (i, 1, S, 1) {
if (!b[i].size()) continue;
vector<ll> h = f;
//cout << b[i].size() << ' ';
fto (weight, 0, S, 1) {
int total = 0;
fdto (t, weight, 0, i) {
if (g[i].size() == total) break;
f[weight] = max(f[weight], h[t] + g[i][total]);
total++;
}
}
}
ll ans = 0;
/*fto (i, 0, S, 1) {
cout << f[i] << '\n';
}*/
fto (i, 0, S, 1) ans = max(f[i], ans);
cout << ans << '\n';
return 0;
}
