#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int S, N, a, b, c; cin >> S >> N;
vector<pair<int, int>> things;
vector<vector<pair<int, int>>> items(S + 1, vector<pair<int, int>>());
for (int i = 0; i < N; i++) {
cin >> a >> b >> c;
items[b].push_back({ a, c });
}
for (int i = 0; i < S; i++) {
sort(items[i + 1].begin(), items[i + 1].end());
for (int j = 0; j < S / (i + 1) && items[i + 1].size(); j++) {
items[i + 1].back().second--;
things.push_back({ items[i + 1].back().first, i + 1 });
if (items[i + 1].back().second == 0) items[i + 1].pop_back();
}
}
vector<vector<int>> dp(things.size(), vector<int>(S + 1, 0));
for (int i = things[0].second; i <= S; i++) dp[0][i] = things[0].first;
for (int i = 1; i < things.size(); i++) {
for (int j = 0; j <= S; j++) {
if (j < things[i].second) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - things[i].second] + things[i].first);
}
}
cout << dp.back().back() << '\n';
}
