#include <bits/stdc++.h>
#define len(x)(int)(x).size()
#define MP make_pair
using namespace std;
const int64_t INFLL = (int64_t)1e18;
const int MAX_N = 2000;
auto get_groups(auto total_w, const auto& arr) {
map<int, vector<pair<int, int>>> w_to_costs;
for (auto [cost, w, cnt] : arr) {
w_to_costs[w].push_back(MP(cost, cnt));
}
map<int, vector<int>> groups;
for (auto &[w, costs] : w_to_costs) {
sort(costs.rbegin(), costs.rend());
int max_len = total_w / w;
int current_cost = costs.front().first, remaining = costs.front().second, i = 0;
while (len(groups[w]) < max_len) {
if (remaining == 0) {
if (i + 1 < len(costs)) {
current_cost = costs[++i].first;
remaining = costs[i].second;
} else {
break;
}
} else {
groups[w].push_back(current_cost);
remaining--;
}
}
}
return groups;
}
void solve() {
int total_w, n;
cin >> total_w >> n;
vector<array<int, 3>> arr(n);
for (auto &arri : arr) {
cin >> arri[0] >> arri[1] >> arri[2];
}
map<int, vector<int>> groups = get_groups(total_w, arr);
vector<vector<int64_t>> dp(total_w + 1, vector<int64_t>(MAX_N + 1, 0));
dp[0][0] = 0;
vector<int64_t> greatest(total_w + 1, -INFLL);
greatest[0] = 0;
for (auto &[w, costs] : groups) {
vector<pair<int, int64_t>> deltas;
int64_t prefix_costs = 0, prefix_w = 0;
for (int cost : costs) {
prefix_costs += cost;
prefix_w += w;
deltas.push_back(MP(prefix_w, prefix_costs));
}
// cout << w << "\n";
// for (auto [dw, dc] : deltas) {
// cout << "\t" << dw << " " << dc << "\n";
// }
auto greatest_updated = greatest;
for (int tw = 1; tw < len(greatest); tw++) {
for (auto [dw, dc] : deltas) {
if (tw - dw < 0 or greatest[tw - dw] == -INFLL) {
continue;
}
greatest_updated[tw] = max(greatest_updated[dw], greatest[tw - dw] + dc);
}
}
greatest = greatest_updated;
}
cout << *max_element(greatest.begin(), greatest.end()) << "\n";
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
