#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using LL = long long;
int main() {
cin.tie(nullptr)->ios_base::sync_with_stdio(false);
LL s, n;
cin >> s >> n;
vector < vector < pair <int, int> > > weight (s + 1);
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
weight[w].push_back ({v, k});
}
for (int i = 1; i <= s; i++) sort (weight[i].rbegin (), weight[i].rend ());
vector <LL> dp (s + 1), ndp (s + 1);
for (LL i = 1; i <= s; i++) {
for (LL j = s; j >= 0; j--) {
ndp[j] = dp[j];
LL k = 1, profit = 0;
for (auto [v, copy] : weight[i]) {
for (LL p = 0; p < copy and k * i <= s and k * i <= j; k++, p++) {
profit += v;
ndp[j] = max (ndp[j], dp[j - k * i] + profit);
}
}
}
swap (dp, ndp);
}
cout << *max_element (all (dp)) << '\n';
return 0;
}
