#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];
if (n == 1) {
cout << (min(c / w[0], k[0]) * v[0]) << "\n";
return 0;
}
ll total = 0; for (auto x: k) total += x;
vector<ll> vt, wt;
for (ll i = 0; i < n; i++) {
ll copy = k[i], currpow = 0;
while (copy > 0) {
ll next = min((ll) pow(2, currpow), (ll) copy);
vt.push_back(v[i] * next);
wt.push_back(w[i] * next);
copy -= pow(2, currpow);
currpow++;
}
}
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);
}
