#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
ll s, n;
cin >> s >> n;
map<ll, vector<pll>> wToItems;
for (ll i = 0; i < n; i++) {
ll v, w, k;
cin >> v >> w >> k;
wToItems[w].push_back({v, k});
}
vector<ll> dp(s + 1, LLONG_MIN);
dp.at(0) = 0;
for (auto p : wToItems) {
ll total = 0; // cap at floor(S / w), where w is the weight
ll index = 0, w = p.first, f = (ll) floor(s / w);
sort(p.second.begin(), p.second.end(), [](const pll &a, const pll &b) {
return a.first > b.first;
});
while (total < f && index < p.second.size()) {
ll v = p.second.at(index).first, k = min(p.second.at(index).second, f - total);
for (ll j = s; j >= 0; j--) {
for (ll kk = 1; (kk <= k) && (j - w * kk >= 0); kk++) {
if (dp.at(j - w * kk) != LLONG_MIN) dp.at(j) = max(dp.at(j), dp.at(j - w * kk) + v * kk);
}
}
total += k;
index++; // next item of the same weight!
}
}
ll ans = 0;
for (ll i : dp) ans = max(ans, i);
cout << ans << endl;
return 0;
}
