#ifdef LOCAL
#include ".debug.hpp"
#else
#define debug(...) 42
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
signed main() {
#ifndef VOID
cin.tie(nullptr)->sync_with_stdio(false);
#endif
int N, S; cin >> S >> N;
vector<vector<int>> group(S + 5);
vector<vector<array<int, 2>>> A(S + 5);
for (int i = 0, V, W, K; i < N; i++) {
cin >> V >> W >> K, K = min(K, S);
A[W].push_back({V, K});
}
for (int w = 1; w <= S; w++) {
if (A[w].empty()) continue;
sort(A[w].begin(), A[w].end(), [&](const array<int, 2> &x, const array<int, 2> &y) -> bool {
return x[0] > y[0];
});
for (auto &[val, cnt] : A[w])
while ((int)group[w].size() <= S / w && cnt-- > 0) group[w].push_back(val);
}
vector<int64_t> dp(S + 5);
for (int w = 1; w <= S; w++)
for (auto &v : group[w])
for (int s = S; s >= w; s--) dp[s] = max(dp[s], dp[s - w] + v);
cout << *max_element(dp.begin(), dp.end());
return 0;
}
