#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
ll bpow(ll a, ll b) {
ll ans = 1, temp = a % MOD;
while (b) {
if (b & 1) ans = ans * temp % MOD;
temp = temp * temp % MOD;
b >>= 1;
}
return ans;
}
ll divide(ll a, ll b) {
return (a % MOD) * bpow(b, MOD - 2) % MOD;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
ll s, n;
cin >> s >> n;
vector<ll> v(n), w(n), k(n);
for (ll i = 0; i < n; i++) cin >> v.at(i) >> w.at(i) >> k.at(i);
vector<ll> dp(s + 1, INT_MIN);
dp.at(0) = 0;
for (ll i = 0; i < n; i++) {
// cout << "w.at(i) = " << w.at(i) << endl;
// cout << "k.at(i) = " << k.at(i) << endl;
for (ll j = s; j >= 0; j--) {
for (ll kk = 1; (kk <= k.at(i)) && (j - w.at(i) * kk >= 0); kk++) {
if (dp.at(j - w.at(i) * kk) != INT_MIN) dp.at(j) = max(dp.at(j), dp.at(j - w.at(i) * kk) + v.at(i) * kk);
}
}
/*
for (ll j = 0; j <= s; j++) {
if (dp.at(j) > 0) cout << "{" << j << ", " << dp.at(j) << "} ";
}
cout << endl;
*/
}
ll ans = 0;
for (ll i : dp) ans = max(ans, i);
cout << ans << endl;
return 0;
}
