#pragma GCC optimize("O3,inline,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).begin(), (v).end()
#define debug cerr << "[DEBUG] "
const char wp = ' ';
const char nl = '\n';
void kebin() {
ll s, n;
cin >> s >> n;
vector<tuple<ll, ll, ll>> arr(n);
for (auto &[a, b, c] : arr) {
cin >> a >> b >> c;
// {value, weight, number (or copies)}
}
vector<ll> ans(s+1);
vector<pair<ll,ll>> dp;
dp.push_back({0, 0});
// prolly the dumbest idea
ll res = 0;
for (auto [val, wei, cnt] : arr) {
for (int i = 1; i <= cnt and i * wei <= s; i++) {
auto nw = vector<pair<ll,ll>>();
for (auto [acc_w, acc_val] : dp) {
ll nwei = acc_w + wei;
if (nwei > s) continue;
if (ans[nwei] < acc_val + val) {
ans[nwei] = acc_val + val;
res = max(res, ans[nwei]);
nw.push_back({nwei, acc_val + val});
}
}
dp.insert(dp.end(), all(nw));
}
}
cout << res << nl;
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--) kebin();
}
