#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int S, N;
cin >> S >> N;
// 1. Group items by weight
map<int, vector<int>> weight_groups;
for (int i = 0; i < N; i++) {
int v, w, k;
cin >> v >> w >> k;
// Optimization: For a weight w, we can take at most S/w items
// so we store all instances of this value up to the capacity limit.
for (int j = 0; j < k && (j + 1) * w <= S; j++) {
weight_groups[w].push_back(v);
}
}
vector<long long> dp(S + 1, 0);
// 2. Process each weight group
for (auto const& [w, values] : weight_groups) {
vector<int> sorted_vals = values;
// Sort descending: we want the most valuable items first
sort(sorted_vals.rbegin(), sorted_vals.rend());
// Use binary splitting on the limited set of items for this weight
// This is much faster than splitting 100,000 individual inputs.
int k_total = sorted_vals.size();
for (int j = 1; k_total > 0; j <<= 1) {
int num_to_take = min(j, k_total);
long long val_sum = 0;
for (int count = 0; count < num_to_take; count++) {
val_sum += sorted_vals.back();
sorted_vals.pop_back();
}
long long weight_sum = (long long)num_to_take * w;
for (int curr_s = S; curr_s >= weight_sum; curr_s--) {
dp[curr_s] = max(dp[curr_s], dp[curr_s - weight_sum] + val_sum);
}
k_total -= num_to_take;
}
}
cout << dp[S] << endl;
return 0;
}
