#include<bits/stdc++.h>
using namespace std;
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int s, n;
cin >> s >> n;
vector<array<int, 2>> items[s + 1];
for(int i = 0; i < n; ++i) {
int v, w, k;
cin >> v >> w >> k;
if(w == 0 || k == 0) {
return 1;
}
items[w].push_back({v, k});
}
for(int i = 1; i <= s; ++i) {
sort(begin(items[i]), end(items[i]));
reverse(begin(items[i]), end(items[i]));
}
int dp[s + 1][2];
memset(dp, 0, sizeof(dp));
int ans = 0;
for(int i = 1; i <= s; ++i) {
for(int j = 0; j <= s; ++j) {
dp[j][1] = 0;
}
int k = 0, sum = 0;
for(int j = i; j <= s && k < (int) items[i].size(); j += i) {
sum += items[i][k][0];
--items[i][k][1];
if(!items[i][k][1]) {
++k;
}
for(int u = j; u <= s; ++u) {
dp[u][1] = max(dp[u][1], dp[u - j][0] + sum);
}
}
for(int j = 0; j <= s; ++j) {
dp[j][0] = max(dp[j][0], dp[j][1]);
}
}
for(int i = 0; i <= s; ++i) {
ans = max(ans, dp[i][0]);
}
cout << ans << '\n';
return 0;
}
