#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 24;
int n, s; int v[N], w[N], k[N];
int dp[N]; vector<int> V[N];
void solve() {
cin >> s >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i] >> k[i];
}
vector<int> id;
for (int i = 1; i <= n; i++) {
id.push_back(i);
}
sort(id.begin(), id.end(), [&] (int i, int j) { return v[i] > v[j]; });
for (int i: id) {
int sz = s / w[i];
while ((int) V[w[i]].size() < sz && k[i] > 0) {
V[w[i]].push_back(v[i]);
k[i]--;
}
}
for (int w = 1; w <= s; w++) {
for (int i = s; i >= w; i--) {
int cnt = 0, v = 0;
for (int x: V[w]) { cnt++; v += x;
if (i - w * cnt < 0) break;
dp[i] = max(dp[i], dp[i - w * cnt] + v);
}
}
}
cout << dp[s] << '\n';
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int T = 1; // cin >> T;
while (T--) {
solve();
}
}
