#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define tii tuple<int, int, int>
// #define f first
// #define s second
#define ve vector
#define emb emplace_back
#define em emplace
using namespace std;
const int inf = 1e18;
const int mod = 1e9 + 7;
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int s, n;
cin >> s >> n;
ve<priority_queue<pii>> pq(s+1);
while (n--) {
int v, w, k;
cin >> v >> w >> k;
k = min(k, s);
pq[w].em(v, k);
}
ve<priority_queue<int>> a(s+1);
for (int i = 1; i <= s; i++) {
int rem = s;
while (!pq[i].empty() && rem) {
auto [val, cnt] = pq[i].top();
pq[i].pop();
if (cnt > rem) cnt = rem;
rem -= cnt;
while (cnt--) a[i].em(val);
}
}
ve<int> dp(s+1, 0);
for (int i = 1; i <= s; i++) {
while (!a[i].empty()) {
auto t = a[i].top();
a[i].pop();
for (int j = s - i; j >= 0; j--) dp[i+j] = max(dp[i+j], dp[j] + t);
}
}
cout << dp[s];
}
