#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
constexpr int maxs = 2e3 + 1;
pii dp[maxs];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int s, n;
cin >> s >> n;
vector <vector <pii>> items(s + 1);
int a, b, c;
for (int i = 0; i < n; i++)
{
cin >> a >> b >> c;
items[b].emplace_back(a, c);
}
for (auto &p : items) sort(p.begin(), p.end());
// v w k
ll nval;
for (int si = 1; si <= s; si++)
{
if (items[si].empty()) continue;
nval = 0;
for (int k = 1; k * si <= s; k++)
{
nval += items[si].back().first;
for (int p = 0; p <= s - k * si; p++)
{
dp[p + k * si].second = max(dp[p + k * si].second, dp[p].first + nval);
}
items[si].back().second--;
if (items[si].back().second == 0)
{
items[si].pop_back();
if (items[si].empty()) break;
}
}
for (int p = 0; p <= s; p++) {
dp[p].first = dp[p].second;
// cout << dp[p].first << " ";
}
}
cout << (*max_element(begin(dp), end(dp))).first << "\n";
}
/*
for position:
for weight:
pos + w = max(pos + value)
*/
