#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, T;
cin >> S >> T;
// Read all item types and group by weight:
// by_weight[w] = vector of (value, count) for items of weight w
map<int, vector<pair<int,int>>> by_weight;
for (int t = 0; t < T; t++) {
int v, w, cnt;
cin >> v >> w >> cnt;
if (w <= S && cnt > 0) {
by_weight[w].emplace_back(v, cnt);
}
}
// Prepare grouped & truncated lists:
// Each entry in `groups` is (weight w, vector of best values)
vector<pair<int, vector<int>>> groups;
for (auto &kv : by_weight) {
int w = kv.first;
auto &items = kv.second;
// Sort by descending value
sort(items.begin(), items.end(),
[](auto &a, auto &b){ return a.first > b.first; });
// We only need up to floor(S / w) copies
int cap = S / w;
vector<int> bestVals;
bestVals.reserve(cap);
// Take counts from the highest-value items first
for (auto &vc : items) {
int v = vc.first;
int c = vc.second;
int take = min(c, cap - (int)bestVals.size());
for (int i = 0; i < take; i++) {
bestVals.push_back(v);
}
if ((int)bestVals.size() == cap) break;
}
if (!bestVals.empty()) {
groups.emplace_back(w, move(bestVals));
}
}
// DP arrays: dp_prev[s] = best value for weight exactly s using processed groups
const ll NEG_INF = LLONG_MIN / 4;
vector<ll> dp_prev(S+1, NEG_INF), dp_curr(S+1, NEG_INF);
dp_prev[0] = 0;
// Process each group
for (auto &grp : groups) {
int w = grp.first;
auto &vals = grp.second;
int m = vals.size();
// Build prefix sums of the values: P[k] = sum of first k vals
vector<ll> P(m+1, 0);
for (int i = 0; i < m; i++) {
P[i+1] = P[i] + vals[i];
}
// Reset dp_curr
fill(dp_curr.begin(), dp_curr.end(), NEG_INF);
// For each possible total weight s:
for (int s = 0; s <= S; s++) {
// Option 1: take 0 items from this group
dp_curr[s] = dp_prev[s];
// Option 2: take k items (1 ≤ k ≤ min(m, s/w))
int maxK = min(m, s / w);
for (int k = 1; k <= maxK; k++) {
ll prev = dp_prev[s - k*w];
if (prev != NEG_INF) {
dp_curr[s] = max(dp_curr[s], prev + P[k]);
}
}
}
// Move to next group
dp_prev.swap(dp_curr);
}
// The answer is the maximum value for any weight ≤ S
ll answer = *max_element(dp_prev.begin(), dp_prev.end());
cout << answer << "\n";
return 0;
}
