#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int pref[2010][2010], dp[2010][2010];
int main() {
int n, s;
cin >> s >> n;
vector<vector<pair<int, int>>> a(s + 1);
for (int i = 0; i < n; ++i) {
int v, w, k;
cin >> v >> w >> k;
a[w].push_back({ v, k });
}
for (int i = 1; i <= s; ++i) sort(a[i].rbegin(), a[i].rend());
for (int i = 1; i <= s; ++i) {
if (a[i].empty()) continue;
int ctr = 1, term = 0, sz = a[i].size(), rem = 1;
while (ctr <= s && term < sz) {
pref[i][ctr] = pref[i][ctr - 1] + a[i][term].first;
++ctr;
++rem;
if (rem > a[i][term].second) {
rem = 1;
++term;
}
}
}
for (int i = 1; i <= s; ++i) {
//consider putting objects of weight i
for (int j = 1; j <= s; ++j) dp[i][j] = dp[i - 1][j];
for (int j = 1; j <= s; ++j) {
for (int k = 1; i * k <= j; ++k) dp[i][j] = max(dp[i][j], dp[i - 1][j - i * k] + pref[i][k]);
}
}
cout << dp[s][s];
}
