#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 5, inf = 1e9, mod = 998244353;
long long dp[100006][2005], s, n;
vector<pair<int, int>> arr[2005];
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
cin >> s >> n;
for (int i = 1; i <= n; i++)
{
int x, y, z;
cin >> x >> y >> z;
arr[y].push_back({x, z});
}
for (int i = 1; i <= s; i++)
for (int j = 0; j <= s; j++)
dp[i][j] = -inf;
for (int i = 1; i <= s; i++)
{
sort(arr[i].begin(), arr[i].end());
for (int j = 0; j <= s; j++)
{
dp[i][j] = dp[i - 1][j];
long long rem = j, points = 0;
int p = arr[i].size() - 1, took = 0;
while (p >= 0 && rem >= 0)
{
if (rem - i < 0)
break;
rem -= i;
points += arr[i][p].first;
took++;
if (arr[i][p].second == took)
p--, took = 0;
dp[i][j] = max(dp[i][j], dp[i - 1][rem] + points);
}
}
}
cout << dp[s][s] << "\n";
}
