#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) {
for (int j = 31; j >= 0; --j) {
if (k[i] & (1 << j)) {
lli cur_w = (1LL << j) * (lli) w[i];
lli cur_v = (1LL << j) * (lli) v[i];
items.emplace_back(cur_w, cur_v);
}
}
}
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;
}
