#include <bits/stdc++.h>
using namespace std;
#define between(l,x,r) ((l) <= (x) && (x) <= (r))
#define len(v) (i64((v).size()))
using i64 = long long;
const i64 MaxN = 1e5;
const i64 MaxS = 2e3;
i64 S, N;
array<i64,3> VWK[MaxN];
vector<i64> VByWeight[MaxS+1];
// (V, W)
vector<pair<i64,i64>> flatten;
i64 DPi[MaxS + 1], DPiplusone[MaxS + 1];
signed main() {
fill(VByWeight, VByWeight + MaxS + 1, vector<i64>(0));
cin >> S >> N;
for (i64 i = 0; i < N; i++) cin >> VWK[i][0] >> VWK[i][1] >> VWK[i][2];
sort(VWK, VWK + N, greater<array<i64,3>>());
for (i64 i = 0; i < N; i++) {
i64 v = VWK[i][0], w = VWK[i][1], k = VWK[i][2];
i64 timesToAdd = min(k, S/w - len(VByWeight[w]));
for (i64 j = 0; j < timesToAdd; j++) {
VByWeight[w].push_back(v);
}
}
for (i64 w = 0; w <= S; w++) {
for (i64 v : VByWeight[w]) {
flatten.push_back({v, w});
}
}
for (i64 i = len(flatten) - 1; i >= 0; i--) {
for (i64 curS = 0; curS <= S; curS++) {
i64 r1 = DPiplusone[curS];
i64 r2 = curS >= flatten[i].second ? DPiplusone[curS - flatten[i].second] + flatten[i].first : 0;
DPi[curS] = max(r1, r2);
}
copy(DPi, DPi + S + 1, DPiplusone);
fill(DPi, DPi + S + 1, 0);
}
i64 res = DPiplusone[S];
cout << res;
return 0;
}
