#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int s, n; cin >> s >> n;
vector<vector<int>> a(n, vector<int>(3));
vector<vector<pair<int, int>>> val(s + 1);
for (auto& x : a) cin >> x[0] >> x[1] >> x[2];
for (int i = 0; i < n; ++i)
val[a[i][1]].push_back({a[i][0], i});
for (int i = 0; i <= s; ++i)
sort(val[i].begin(), val[i].end(), greater<pair<int, int>>());
vector<int> idx;
for (int i = 0; i <= s; ++i) {
int cur = 0;
for (int j = 0; j < val[i].size(); ++j) {
auto c = val[i][j];
cur += a[c.second][2];
a[c.second][2] -= max(0ll, cur - s);
idx.push_back(c.second);
if (cur >= s) break;
}
}
vector<pair<int, int>> arr;
for (auto x : idx)
for (int i = 0; i < a[x][2]; ++i)
arr.push_back(make_pair(a[x][0], a[x][1]));
n = arr.size();
vector<vector<int>> dp(n, vector<int>(s + 1));
for (int i = arr[0].second; i <= s; ++i) dp[0][i] = arr[0].first;
for (int i = 1; i < n; ++i)
for (int j = 0; j <= s; ++j)
dp[i][j] = max(dp[i - 1][j], ((j >= arr[i].second) ? dp[i - 1][j - arr[i].second] : 0ll) + arr[i].first);
cout << dp[n - 1][s];
}
