#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long S, N;
cin >> S >> N;
// weight -> vector of values
unordered_map<long long, vector<long long>> groups;
groups.reserve(N);
groups.max_load_factor(0.7f);
for(int i = 0; i < N; i++){
long long V, W, K;
cin >> V >> W >> K;
// We cannot take more than floor(S / W) copies of this item anyway
long long limit = S / W;
// So among K copies, we only need to keep min(K, limit) of them.
long long take = min(K, limit);
// Push those 'take' copies of value V into groups[W].
// (Because subtask constraints allow S up to 2000, this is safe enough.)
for(int c = 0; c < take; c++){
groups[W].push_back(V);
}
}
// Now, for each weight group, sort values in descending order and truncate
// to at most floor(S / W) items (in case multiple lines gave the same weight).
vector<long long> finalWeights, finalValues;
finalWeights.reserve(S * 30); // just a small over-reservation
finalValues.reserve(S * 30);
for(auto &kv : groups) {
long long w = kv.first;
auto &vals = kv.second;
sort(vals.begin(), vals.end(), greater<long long>());
// cap again at floor(S / w) in case multiple input lines had the same weight
long long limit = S / w;
if((long long)vals.size() > limit) {
vals.resize(limit);
}
// store in final arrays
for(long long v : vals) {
finalWeights.push_back(w);
finalValues.push_back(v);
}
}
// Now do a standard 0-1 knapsack on (finalWeights, finalValues)
vector<long long> dp(S + 1, 0);
for(int i = 0; i < (int)finalWeights.size(); i++) {
long long w = finalWeights[i], val = finalValues[i];
for(long long cap = S; cap >= w; cap--) {
dp[cap] = max(dp[cap], dp[cap - w] + val);
}
}
cout << dp[S] << "\n";
return 0;
}
