#include <bits/stdc++.h>
#include <chrono>
#define ll long long int
#define endl '\n'
#define vn vector<ll>
#define vi vector<pair<ll,ll>>
using namespace std;
using namespace std::chrono;
const int MAX_N = 1e9 + 7;
#define pii pair<ll,ll>
const ll INF = 0x3f3f3f3f3f3f3f3f;
#define pb push_back
#define srt(vp) sort(vp.begin(), vp.end())
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
auto start = high_resolution_clock::now();
ll s, n;
cin >> s >> n;
vector<vector<pair<ll,ll>>> v(s + 1); // group by weight
for (int i = 0; i < n; i++) {
ll a, b, c;
cin >> a >> b >> c; // value, weight, copies
v[b].pb({a, c});
}
// For each weight group, keep top floor(s/weight) items
for (int i = 1; i <= s; i++) {
if (v[i].empty()) continue;
// sort by value descending
sort(v[i].rbegin(), v[i].rend());
ll limit = s / i; // max items of this weight we could use
ll curr = 0, it = 0;
while (curr < limit && it < (ll)v[i].size()) {
if (curr + v[i][it].second <= limit) {
curr += v[i][it].second;
it++;
} else {
v[i][it].second = limit - curr;
curr = limit;
}
}
if (it < (ll)v[i].size()) {
v[i].erase(v[i].begin() + it, v[i].end());
}
}
// Build query items (each copy as 0/1 item)
vector<pair<ll,ll>> query;
for (int i = 1; i <= s; i++) {
for (auto &x : v[i]) {
for (int k = 0; k < x.second; k++) {
query.pb({x.first, i}); // (value, weight)
}
}
}
vn dp(s + 1, -1);
dp[0] = 0;
// 0/1 knapsack
for (auto &q : query) {
ll val = q.first, w = q.second;
for (int j = s; j >= w; j--) {
if (dp[j - w] != -1) {
dp[j] = max(dp[j], dp[j - w] + val);
}
}
}
cout << dp[s] << endl;
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
return 0;
}
