#include <bits/stdc++.h>
using namespace std;
#define D(x) cerr << #x << " = " << x << ", "
using vi = vector<int>;
using vvi = vector<vi>;
struct Elem {
int v, w, k;
int order() const {
return -v;
}
};
bool operator<(const Elem& lhs, const Elem& rhs) {
return lhs.order() < rhs.order();
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int s, n;
cin >> s >> n;
vector<vector<Elem>> elems(s+1);
for (int i = 0; i < n; ++i) {
Elem e;
cin >> e.v >> e.w >> e.k;
elems[e.w].push_back(e);
}
for (int w = 1; w <= s; ++w) {
sort(elems[w].begin(), elems[w].end());
}
vvi dp(s+1, vi(s+1));
int ans = 0;
for (int w = 1; w <= s; ++w) {
for (int j = 0; j <= s; ++j) {
dp[w][j] = dp[w-1][j];
int acum = 0;
int space = 0;
for (Elem e : elems[w]) {
for (int it = 0; it < e.k; ++it) {
acum += e.v;
space += w;
if (space > j) break;
dp[w][j] = max(dp[w][j], dp[w-1][j-space] + acum);
}
if (space > j) break;
}
}
ans = max(ans, dp[w][s]);
}
cout << ans << endl;
}
