#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define all(v) v.begin(), v.end()
using namespace std;
using pii = pair<int, int>;
int s, n;
vector<vector<int>> val;
vector<int> dp;
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> s >> n;
val.resize(s + 1);
while (n--) {
int v, w, k;
cin >> v >> w >> k;
int x = 1;
while (x <= k) {
if (w * x <= s) val[w * x].push_back(v * x);
k -= x;
x <<= 1;
}
if (k && w * k <= s) val[w * k].push_back(v * k);
}
for (int i = 1; i <= s; ++i) {
sort(all(val[i]), greater<int>());
int len = val[i].size();
val[i].insert(val[i].begin(), 0);
for (int j = 1; j <= len; ++j) {
val[i][j] += val[i][j - 1];
}
}
dp.assign(s + 1, 0);
for (int i = 1; i <= s; ++i) {
for (int j = s; j >= i; --j) {
for (int k = 1; k < val[i].size(); ++k) {
if (j >= i * k) {
dp[j] = max(dp[j], dp[j - i * k] + val[i][k]);
} else {
break;
}
}
}
}
cout << dp[s];
}
