#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define tlll tuple<ll, ll, ll>
#define pll pair<ll, ll>
int main()
{
ll s, n;
cin >> s >> n;
vector<tlll> vs;
for (ll i = 0; i < n; i++) {
ll v, w, k;
cin >> v >> w >> k;
vs.push_back(make_tuple(w, v, k));
}
sort(vs.begin(), vs.end());
vector<ll> vw;
vector<vector<pll>> vv;
ll si = 0;
for (ll i = 0; i < n; i++) {
ll w, v, k;
tie(w, v, k) = vs[i];
if (i == 0 || w != get<0>(vs[i-1])) {
vw.push_back(w);
vv.push_back({});
si++;
}
vv[si-1].push_back(make_pair(v, k));
}
vector<ll> ks(s+1, 0);
for (ll i = 0; i < si; i++) {
sort(vv[i].rbegin(), vv[i].rend());
ll most = s/vw[i];
ll seen = 0;
ll j = 0;
while (seen < most && j < (ll) vv[i].size()) {
for (ll a = s; a >= vw[i]; a--) {
ks[a] = max(ks[a], ks[a-vw[i]]+vv[i][j].first);
}
vv[i][j].second--;
if (vv[i][j].second == 0) j++;
seen++;
}
}
ll maxi = 0;
for (ll v : ks) maxi = max(maxi, v);
cout << maxi;
return 0;
}
