#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << '\n')
#define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << " "); PRINT("}\n");)
typedef int64_t i64;
const int INF = 1000000007; //998244353;
struct T3 {
i64 v;
i64 w;
i64 k;
};
struct S {
int s, n;
vector<T3> a;
void run() {
cin >> s >> n;
a.resize(n);
for (int i = 0; i < n; ++i) {
cin >> a[i].v >> a[i].w >> a[i].k;
}
sort(a.begin(), a.end(), [&](T3 &x, T3 &y) {
if (x.w != y.w) return x.w < y.w;
if (x.v != y.v) return x.v > y.v;
return x.k < y.k;
});
vector<i64> cur(s + 1, -1), prev(s + 1, -1), cnt(s + 1, 0);
cur[0] = 0; prev[0] = 0;
for (int i = 0; i < n; ++i) {
PAR(prev);
for (int j = 0; j + a[i].w <= s; ++j) {
if (cur[j] == -1) continue;
if (make_pair(cur[j + a[i].w], -cnt[j + a[i].w])
< make_pair(cur[j] + a[i].v, -cnt[j] - 1)
&& cnt[j] < a[i].k) {
PRINT(' '); PV(j);
cur[j + a[i].w] = cur[j] + a[i].v;
cnt[j + a[i].w] = cnt[j] + 1;
} else if (prev[j] != -1 && cur[j + a[i].w] < prev[j] + a[i].v) {
PV(j);
cur[j + a[i].w] = prev[j] + a[i].v;
cnt[j + a[i].w] = 1;
}
}
PAR(cur);
PAR(cnt);
prev = cur;
fill(cnt.begin(), cnt.end(), 0);
}
i64 ans = 0;
for (int i = 0; i <= s; ++i) {
ans = max(ans, cur[i]);
}
cout << ans << '\n';
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
auto sol = make_unique<S>();
sol->run();
}
