#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, s;
cin >> s >> n;
vector<int> v(n), w(n), k(n), dp(s + 1);
for (int i = 0; i < n; i++) cin >> v[i] >> w[i] >> k[i];
vector<vector<pair<int, int>>> W(s + 1);
for (int i = 0; i < n; i++) {
if (w[i] <= s) W[w[i]].emplace_back(v[i], k[i]);
}
for (int i = 0; i <= s; i++) sort(W[i].rbegin(), W[i].rend());
for (int i = 1; i <= s; i++) {
auto ndp = dp;
for (int j = 1; j <= s; j++) {
int cw = 0, jj = j;
for (auto [x, y] : W[i]) {
int yy = y;
// if (j == s) cout << x << ' ' << y << '\n';
for (;;) {
// if (j == s) cout << "jj: " << jj << " yy: " << yy << " cw: " << cw << '\n';
if (jj - i >= 0 && yy - 1 >= 0) jj -= i, yy--, cw += x, ndp[j] = max(ndp[j], dp[jj] + cw);
else break;
}
}
}
dp = ndp;
// for (int i : dp) cout << i << ' ';
// cout << '\n';
}
cout << *max_element(dp.begin(), dp.end()) << '\n';
return 0;
}
