#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);
vector<bool> vis(s + 1, 0);
for (int i = 0; i < n; i++) {
ll a, b, c;
cin >> a >> b >> c;
vis[b] = true;
v[b].pb({a, c});
}
for (int i = 1; i <= s; i++) {
if (!vis[i]) continue;
sort(v[i].rbegin(), v[i].rend());
ll num = s / i;
ll curr = 0;
ll it = 0;
while (curr < num && it < (ll)v[i].size()) {
if (curr + v[i][it].second <= num) {
curr += v[i][it].second;
it++;
} else {
v[i][it].second = num - curr;
curr = num;
}
}
if (it < (ll)v[i].size())//imp check
v[i].erase(v[i].begin() + it, v[i].end());
}
vector<tuple<ll,ll,ll>> query;
for (int i = 1; i <= s; i++) {
for (auto &x : v[i]) {
query.pb({x.first, i, x.second});
}
}
vn dp(s + 1, -1);
dp[0] = 0;
for (int i = 0; i < (ll)query.size(); i++) {
for (int k = 1; k <= get<2>(query[i]); k++) {
ll temp = get<1>(query[i]) * k;
for (int j = s; j >= temp; j--) {
if (dp[j - temp] == -1) continue;
dp[j] = max(dp[j], dp[j - temp] + k * get<0>(query[i]));
}
}
}
cout << dp[s] << endl;
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
return 0;
}
