#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int s, n;
cin >> s >> n;
vector<vector<pair<int, int>>> br(s + 1);
for (int i = 0; i < n; i++) {
int r, v, k;
cin >> r >> v >> k;
br[v].push_back({r, k});
}
vector<pair<int, long long>> cc;
for (int i = 1; i <= s; i++) {
sort(br[i].rbegin(), br[i].rend());
int k = s / i;
for (auto [x, y] : br[i]) {
int to = min(k, y);
for (int j = 0; (1 << j) <= to; j++) {
to -= (1 << j);
cc.push_back({(1 << j) * i, (1LL << j) * x});
}
if (to) {
cc.push_back({to * i, (long long) to * x});
}
k -= min(k, y);
if (!k) break;
}
}
vector<long long> dp(s + 1);
for (auto [x, y] : cc) {
for (int j = s; j >= x; j--) {
dp[j] = max(dp[j], dp[j - x] + y);
}
}
cout << dp[s] << '\n';
return 0;
}
