#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve()
{
int mw, n;
cin >> mw >> n;
vector<pair<int, int>> faw[mw + 1];
for (int i = 0; i < n; i++) {
int w, v, a;
cin >> v >> w >> a;
faw[w].push_back({v, a});
}
for (int i = 1; i <= mw; i++) {
sort(faw[i].rbegin(), faw[i].rend());
}
vector<int> aw[mw + 1];
for (int i = 1; i <= mw; i++) {
int ct = mw / i + 1;
for (auto& [v, a] : faw[i]) {
for (int p = 0; p < a; p++) {
aw[i].push_back(v);
ct--;
if (ct == 0) break;
}
if (ct == 0) break;
}
}
int dp[mw + 1];
for (int i = 0; i <= mw; i++) dp[i] = 0;
for (int i = 1; i <= mw; i++) {
int pm = min(mw / i + 1, (int)aw[i].size());
for (int j = 0; j < pm; j++) {
for (int p = mw; p >= i; p--) {
dp[p] = max(dp[p - i] + aw[i][j], dp[p]);
}
}
}
//for (auto& p : dp) cout << p << ' ';
cout << dp[mw];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
/*
*/
