#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> dp(s+1);
for (auto [val, wei, cnt] : arr) {
for (int i = 1; i <= cnt and i * wei <= s; i++) {
for (int w = s; w >= wei; w--) {
dp[w] = max(dp[w], dp[w-wei] + val);
}
}
}
cout << *max_element(all(dp)) << nl;
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--) kebin();
}
