#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll s, n;
vector<ll> v, w, k;
vector<vector<ll>> dp, add;
signed main() {
cin >> s >> n;
v.resize(n);
w.resize(n);
k.resize(n);
dp.assign(n, vector<ll>(s + 1, 0LL));
add.assign(n, vector<ll>(s + 1, 0LL));
for (int i = 0; i < n; i++) {
cin >> v[i] >> w[i] >> k[i];
}
for (int i = 0; i <= s; i++) {
dp[0][i] = min(i / w[0], k[0]) * v[0];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= s; j++) {
dp[i][j] = dp[i-1][j];
if (j > w[i] && k[i] >= add[i][j-w[i]]+1 && dp[i][j-w[i]] + v[i] > dp[i][j]) {
dp[i][j] = dp[i][j-w[i]] + v[i];
add[i][j] = add[i][j-w[i]] + 1;
}
}
}
// for (int i = 0; i< n; i++) {
// for (int j = 0; j <= s; j++) {
// cout << dp[i][j] << ' ';
// }
// cout << '\n';
// }
ll ans = 0;
for (int i = 0; i <= s; i++) {
ans = max(ans, dp[n-1][i]);
}
cout << ans << '\n';
}
