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