#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pll pair<ll, ll>
#define ppll pair< pair<long long, long long>, long long >
#define ff first
#define ss second
#define pb push_back
#define pf push_front
const ll DIM = 1e6 + 7;
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ll maxlog = 20;
const ll bsize = 350;
ll dp[2007][2007];
map<ll, vector<pll> > m;
void solve() {
ll s, n;
cin >> s >> n;
for (int i=1; i<=n; i++) {
ll val, w, k;
cin >> val >> w >> k;
m[w].pb({val, k});
}
ll k = 0;
for (auto [w, v] : m) {
++k;
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
for (int nw = 0; nw <= s; nw++) {
dp[k][nw] = dp[k-1][nw];
ll sumval = 0, i = 0, cur = 0;
for (int p=1; p<=s; p++) {
if (v[i].ss == cur) {
i++;
cur = 0;
if (i == v.size()) break;
}
cur++;
sumval += v[i].ff;
if (w*p > nw) break;
dp[k][nw] = max(dp[k][nw], dp[k-1][nw - w*p] + sumval);
}
}
}
ll ans = 0;
for (int i=s; i>=0; i--) {
ans = max(ans, dp[k][i]);
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int ntest = 1;
//cin >> ntest;
while (ntest--) {
solve();
}
return 0;
}
;
