#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;
#ifdef LOCAL
#include </home/marcus06/vimcp/Library/debug.h>
#else
#define debug(...)
#endif
void solve() {
int n, s;
cin >> s >> n;
vector <int> v(n), w(n), k(n);
for (int i = 0; i < n; ++i) {
cin >> v[i] >> w[i] >> k[i];
}
vector <pair <lli, lli>> items;
for (int i = 0; i < n; ++i) {
int x = 1;
while (k[i] >= x) {
items.emplace_back((lli) x * w[i], (lli) x * v[i]);
k[i] -= x;
x *= 2;
}
items.emplace_back((lli) k[i] * w[i], (lli) k[i] * v[i]);
}
vector <lli> dp(s + 1, 0);
for (auto [w, v]: items) {
for (int i = s; i >= w; --i) dp[i] = max(dp[i], dp[i - w] + v);
}
cout << *max_element(dp.begin(), dp.end()) << '\n';
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
auto begin = std::chrono::high_resolution_clock::now();
#endif
int tt = 1;
while (tt--) {
solve();
}
#ifdef LOCAL
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
#endif
return 0;
}
