// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define f first
#define mp make_pair
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifndef LOCAL
#define endl "\n"
#else
#include "/mnt/c/yukon/pp.hpp"
#endif
int main() {
cin.tie(0)->sync_with_stdio(0);
int max_w, n;
cin >> max_w >> n;
vector<vector<pi>> items(max_w + 1);
for (int i = 0; i < n; i++) {
int w, v, copies;
cin >> v >> w >> copies;
items[w].emplace_back(v, copies);
}
for (int i = 0; i <= max_w; i++) {
sort(rall(items[i]));
}
vector<pair<int, vector<int>>> dp(max_w + 1, mp(-inf, vector<int>(max_w + 1, inf)));
dp[0] = mp(0, vector<int>(max_w + 1, 0));
for (int i = 1; i <= max_w; i++) {
for (int w = i; w >= 1; w--) {
int prev = i - w;
int used_up = dp[prev].s[w];
int gain = 0;
for (int j = 0; j < sz(items[w]); j++) {
if (used_up < items[w][j].s) {
gain = items[w][j].f;
break;
}
used_up -= items[w][j].s;
}
if (gain == 0)
continue;
auto new_dp = dp[prev].s;
new_dp[w]++;
// cout << i << ' ' << prev << endl;
if (dp[prev].f + gain > dp[i].f) {
// cout << "save " << i << " from " << prev << ": " << dp[prev].f << " + " << gain << endl;
dp[i] = {dp[prev].f + gain, new_dp};
}
}
}
int ans = 0;
for (int i = 1; i <= max_w; i++) {
ans = max(ans, dp[i].f);
}
cout << ans << endl;
}
// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)
