#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.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];
// cap multiplicities at 2000 (as in your code)
for (int i = 0; i < n; i++) k[i] = min(k[i], 2000ll);
vector<ll> vt, wt;
for (int i = 0; i < n; i++) {
ll copy = k[i], currpow = 1;
while (copy > 0) {
ll take = min(currpow, copy);
vt.push_back(v[i] * take);
wt.push_back(w[i] * take);
copy -= take;
currpow <<= 1;
}
}
vector<ll> dp(c + 1, 0);
for (size_t i = 0; i < vt.size(); i++) {
for (ll cap = c; cap >= wt[i]; cap--) {
dp[cap] = max(dp[cap], dp[cap - wt[i]] + vt[i]);
}
}
cout << dp[c] << "\n";
}
