#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define BIT(n) (1ll << n)
#define GBIT(x, i) ((x >> i) & 1)
#define all(v) v.begin(), v.end()
#define eb emplace_back
#define pb push_back
#define endl '\n'
#define fu(i, l, r) for (int i = (int) (l); i <= (int) (r); i++)
#define fd(i, r, l) for (int i = (int) (r); i >= (int) (l); i--)
typedef pair <int, int> pii;
typedef pair <long long, long long> pll;
typedef unsigned long long ull;
typedef long long ll;
typedef double dl;
const int MAXN = 4e5 + 55;
const int MOD = 1e9 + 7;
const ll oo = 1ll * MOD * MOD;
int S, n;
struct datastore {
int v, w, k;
} a[MAXN];
void rf() {
cin >> S >> n;
fu(i, 1, n) cin >> a[i].v >> a[i].w >> a[i].k;
}
#define sizeRocket 2005
ll dp[sizeRocket][sizeRocket];
vector <pii> store[sizeRocket];
void solve() {
fu(i, 1, n) store[a[i].w].eb(a[i].v, a[i].k);
memset(dp, -63, sizeof dp);
dp[0][0] = 0;
fu(i, 1, S) {
sort(all(store[i]), greater <pii> ());
int id = 0;
ll val = 0;
int weight = 0;
fu(j, 0, S) dp[i][j] = dp[i - 1][j];
while (id < store[i].size()) {
val += store[i][id].fi;
weight += i;
store[i][id].se--;
if (weight > S) break;
if (0 == store[i][id].se) id++;
fu(j, 0, S) if (j + weight <= S) {
dp[i][j + weight] = max(dp[i][j + weight], dp[i - 1][j] + val);
} else break;
}
// fu(j, 0, S) cout << dp[i][j] << " "; cout << endl;
}
ll res = -oo;
fu(i, 0, S) fu(j, 0, S) res = max(res, dp[i][j]);
cout << res << endl;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "prob"
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int ntest = 1;
// cin >> ntest;
fu(i, 1, ntest) rf(), solve();
}
