#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
uint64_t n, s;
cin >> s >> n;
vector<uint64_t> price(n), weight(n), count(n);
for (int i = 0; i < n; ++i) {
cin >> price[i] >> weight[i] >> count[i];
}
std::unordered_map<uint64_t, std::vector<std::pair<uint64_t, uint64_t>>> max_values;
for (int i = 0; i < n; ++i) {
max_values[weight[i]].push_back({price[i], count[i]});
}
std::unordered_map<uint64_t, std::vector<uint64_t>> prefixes;
for (auto& [k, v] : max_values) {
std::sort(v.rbegin(), v.rend());
std::vector<uint64_t> pre;
pre.push_back(0);
int max_sz = s / k;
for (auto [p, cnt] : v) {
for (int j = 0; j < cnt && max_sz > 0; ++j, --max_sz) {
auto prev = pre.back();
pre.push_back(prev + p);
}
}
prefixes[k] = std::move(pre);
}
std::vector<uint64_t> old_dp(s + 1, 0);
std::vector<uint64_t> new_dp(s + 1, 0);
uint64_t ans = 0;
for (int max_w = 1; max_w <= s; ++max_w) {
for (int cnt = 1; cnt < prefixes[max_w].size(); ++cnt) {
for (int total = max_w * cnt; total <= s; ++total) {
if (total > max_w * cnt && old_dp[total - max_w * cnt] == 0) {
continue;
}
new_dp[total] = max(new_dp[total], old_dp[total - max_w * cnt] + prefixes[max_w][cnt]);
ans = max(ans, new_dp[total]);
}
}
for (int cnt = 1; cnt < prefixes[max_w].size(); ++cnt) {
for (int total = max_w * cnt; total <= s; ++total) {
old_dp[total] = max(old_dp[total], new_dp[total]);
new_dp[total] = 0;
}
}
}
cout << ans;
}
