#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define ff first
#define ss second
#define inp_v(vec) \
for (auto &i : vec) \
cin >> i;
#define prt_v(vec) \
for (auto i : vec) \
cout << i << endl;
#define MS(x) memset(x, 0, sizeof(x))
#define gcd(a, b) __gcd(a, b);
#define lcm(a, b) (a * (b / gcd(a, b)))
#define lb lower_bound
#define ub upper_bound
bool chmin(int &a, int b)
{
return b < a ? a = b, true : false;
}
bool chmax(int &a, int b) { return b > a ? a = b, true : false; }
bool comp(const pair<int, int> &a, const pair<int, int> &b)
{
return a.first > b.first;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, M;
cin >> N >> M;
vector<vector<pair<int, int>>> simp(N + 5), v(N + 5);
for (int i = 0; i < M; i++)
{
int a, b, c;
cin >> a >> b >> c;
simp[b].push_back({a, c});
}
for (int i = 1; i <= N; i++)
{
sort(simp[i].begin(), simp[i].end(), comp);
int cost = 0, val = 0;
bool stat = true;
for (auto j : simp[i])
{
if (!stat)
break;
for (int k = 0; k < j.second; k++)
{
cost += i;
val += j.first;
// cout<<cost<<" "<<val<<endl;
if (cost > N)
{
stat = false;
break;
}
v[i].push_back({val, cost});
}
}
}
int dp[N + 1][N + 1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= N; i++)
{
if (v[i].size())
{
for (auto j : v[i])
{
for (int k = 0; k <= N; k++)
{
if (k >= j.second)
{
dp[i][k] = max(max(dp[i][k], dp[i - 1][k]), dp[i - 1][k - j.second] + j.first);
}
else
{
dp[i][k] = max(dp[i][k], dp[i - 1][k]);
}
}
}
}
else
{
for (int k = 0; k <= N; k++)
{
dp[i][k] = dp[i - 1][k];
}
}
}
cout << dp[N][N] << '\n';
// dp[0][0]=0;
// for(int i=1;i<=N;i++){
// if(tot[i]){
// for(int j=1;j<=N;j++){
// int idx=1, cur=v[i][idx].first, cur2=v[i][idx].second, sz=v[i].size();
// int k=0;
// }
// }
// }
return 0;
}
