/*
author : PakinDioxide
created : 20/04/2025 09:23
task : NOI18_knapsack
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int s, n;
cin >> s >> n;
vector <pair <ll, ll>> V[s+1], A;
for (int i = 0; i < n; i++) {
ll v, w, c;
cin >> v >> w >> c;
V[w].emplace_back(v, c);
}
for (int i = 0; i <= s; i++) {
sort(V[i].begin(), V[i].end());
reverse(V[i].begin(), V[i].end());
int cnt = 0;
for (auto &[x, y] : V[i]) while (y > 0 && cnt*i <= s) A.emplace_back(x, i), cnt++, y--;
}
vector <ll> dp(s+1, LLONG_MIN);
dp[0] = 0;
ll ans = 0;
for (auto &[v, w] : A) for (int i = s; i >= w; i--) dp[i] = max(dp[i], dp[i-w] + v), ans = max(ans, dp[i]);
cout << ans << '\n';
}
