#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
vector<vector<pair<int,long long>>> groups(S + 1);
for (int i = 0; i < N; ++i) {
long long Vi, Wi, Ki;
cin >> Vi >> Wi >> Ki;
if (Wi <= S) groups[Wi].push_back({(int)Vi, Ki});
}
vector<long long> dp(S + 1, 0);
for (int w = 1; w <= S; ++w) {
if (groups[w].empty()) continue;
auto &vec = groups[w];
sort(vec.begin(), vec.end(), [](const pair<int,long long>& a, const pair<int,long long>& b){
return a.first > b.first;
});
int limit = S / w;
vector<long long> single; single.reserve(limit);
for (auto &p : vec) {
long long val = p.first;
long long cnt = p.second;
long long can_take = min<long long>(cnt, limit - (int)single.size());
for (long long t = 0; t < can_take; ++t) single.push_back(val);
if ((int)single.size() == limit) break;
}
if (single.empty()) continue;
int m = single.size();
vector<long long> pref(m + 1, 0);
for (int i = 0; i < m; ++i) pref[i + 1] = pref[i] + single[i];
for (int t = 1; t <= m; ++t) {
int wt = t * w;
long long val = pref[t];
for (int cap = S; cap >= wt; --cap) {
dp[cap] = max(dp[cap], dp[cap - wt] + val);
}
}
}
cout << dp[S] << "\n";
return 0;
}
