#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<ll>> v(s + 1); // group by weight, store values only
for (int i = 0; i < n; i++) {
ll a, b, c;
cin >> a >> b >> c; // value, weight, copies
if (b > s) continue; // weight too big, ignore
for (int k = 0; k < c && k < (s / b); k++) {
v[b].pb(a);
}
}
// Now limit per weight group to top floor(s/w) values
vector<pair<ll,ll>> query; // (value, weight)
for (int w = 1; w <= s; w++) {
if (v[w].empty()) continue;
sort(v[w].rbegin(), v[w].rend());
ll limit = s / w;
if ((ll)v[w].size() > limit) v[w].resize(limit);
for (auto val : v[w]) {
query.pb({val, w});
}
}
vn dp(s + 1, -1);
dp[0] = 0;
// 0/1 knapsack on reduced set
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);
// cerr << "Time: " << duration.count() << " us\n"; // debug timing if needed
return 0;
}
