#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)(1e18) + 13;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int s, n;
cin >> s >> n;
vector<vector<array<int,2>>> W(s+1);
int Q[s+1];
for (int i=0; i<n; i++) {
int v, w, k;
cin >> v >> w >> k;
W[w].push_back({v, k});
Q[w] += k;
}
for (int i=1; i<=s; i++) {
if (W[i].size() > 0) {
sort(W[i].begin(), W[i].end(), [](auto &a, auto &b) {
if (a[0] == b[0]) {
return a[1] > b[1];
}
return a[0] > b[0];
});
}
}
vector<ll> dp(s+5, -INF);
dp[0] = 0;
for (int w=1; w<=s; w++) {
if (W[w].size() == 0) continue;
int T = s / w;
int t = 0;
for (auto &item : W[w]) {
auto [V, K] = item;
for (int i = 0; i < K && t < T; i++) {
for (int j=s; j>=0; j--) {
if (j+w <= s && dp[j] > -INF) {
dp[j+w] = max(dp[j+w], dp[j] + V);
}
}
t++;
}
if (t >= T) break;
}
}
ll ans = 0;
for (int i=0; i<=s; i++) {
ans = max(ans, dp[i]);
}
cout << ans << '\n';
}
