#include<bits/stdc++.h>
using namespace std;
#define int long long
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;
items[w].push_back({v, k});
}
for(int i = 1; i <= s; ++i) {
sort(begin(items[i]), end(items[i]), greater<array<int, 2>>());
}
int dp[s + 1][s + 1];
memset(dp, -1, sizeof(dp));
int ans = 0;
dp[0][0] = 0;
for(int i = 1; i <= s; ++i) {
for(int j = 0; j <= s; ++j) {
dp[i][j] = dp[i - 1][j];
}
int k = 0, sum = 0;
for(int j = i; j <= s; j += i) {
if(k == (int) items[i].size()) {
break;
}
sum += items[i][k][0];
--items[i][k][1];
if(!items[i][k][1]) {
++k;
}
for(int u = j; u <= s; ++u) {
if(dp[i - 1][u - j] != -1) {
dp[i][j] = max(dp[i][j], dp[i - 1][u - j] + sum);
}
}
}
}
for(int i = 0; i <= s; ++i) {
for(int j = 0; j <= s; ++j) {
ans = max(ans, dp[i][j]);
}
}
cout << ans << '\n';
return 0;
}
