#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;
#ifdef LOCAL
#include </home/marcus06/vimcp/Library/debug.h>
#else
#define debug(...)
#endif
void solve() {
int S, N; cin >> S >> N;
vector <vector <pair <int, int>>> groups(S + 1);
for (int i = 0; i < N; ++i) {
int v, w, k;
cin >> v >> w >> k;
groups[w].emplace_back(v, k);
}
for (int i = 1; i <= S; ++i) {
sort(groups[i].begin(), groups[i].end(), greater <pair <int, int>>());
}
vector <vector <lli>> dp(S + 1, vector <lli> (S + 1, 0));
for (int i = 1; i <= S; ++i) {
dp[i] = dp[i - 1];
if (groups[i].empty()) continue;
//only consider S / i items from this set
for (int j = S; j >= 0; --j) {
int cur_w = 0;
lli cur_v = 0;
for (auto [v, k]: groups[i]) {
while (k > 0 && cur_w <= j) {
cur_w += i;
cur_v += v;
--k;
if (j >= cur_w) dp[i][j] = max(dp[i][j], dp[i - 1][j - cur_w] + cur_v);
}
}
}
}
lli ans = *max_element(dp[S].begin(), dp[S].end());
cout << ans << '\n';
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
auto begin = std::chrono::high_resolution_clock::now();
#endif
int tt = 1;
while (tt--) {
solve();
}
#ifdef LOCAL
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
#endif
return 0;
}
