#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll c, n; cin >> c >> n;
vector<ll> v(n), w(n), k(n);
for (int i = 0; i < n; i++) cin >> v[i] >> w[i] >> k[i];
ll total = 0; for (auto x: k) total += x;
vector<ll> vt, wt;
for (ll i = 0; i < n; i++)
for (ll j = 0; j < k[i]; j++)
vt.push_back(v[i]), wt.push_back(w[i]);
map<pll, ll> memo;
function<ll(ll, ll)> f = [&](ll i, ll j) {
if (j < 0) return -9999999999999ll;
if (i < 0) return 0ll;
if (memo.count({i, j})) return memo[{i, j}];
return memo[{i, j}] = max(vt[i] + f(i - 1, j - wt[i]), f(i - 1, j));
};
cout << f(total - 1, c);
}
