#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll MAXT = 2e3 + 5;
ll t, n, dp[MAXT];
vector<pll> vec[MAXT][MAXT];
// Vec[i][j] menyatakan state energi j pada saat energi = i
// {Li, Ki}
int main(){
cin >> t >> n;
for (int i = 1; i <= n; ++i)
{
ll li, ei, ki;
cin >> li >> ei >> ki;
vec[0][ei].push_back({ei, ki});
}
for (int i = 0; i <= t; ++i)
{
if (!vec[0][i].empty())
{
sort(vec[0][i].begin(), vec[0][i].end());
for (int j = 1; j <= t; ++j)
{
vec[j][i] = vec[0][i];
}
}
}
for (int i = 0; i <= t; ++i)
{
pll pake = {-1, -1};
// {i yang mana, j berapa}
for (int j = 0; j <= i; ++j)
{
if (vec[i-j][j].empty())
{
if (dp[i-j] > dp[i])
{
pake = {i-j, -1};
dp[i] = dp[i-j];
}
continue ;
}
ll hasil = dp[i-j] + vec[i-j][j].back().first;
if (hasil > dp[i])
{
pake = {i-j, j};
dp[i] = hasil;
}
}
if (pake.first > -1)
{
if (pake.second > -1)
{
// Kurangi
vec[pake.first][pake.second].back().second--;
if (vec[pake.first][pake.second].back().second == 0)
{
vec[pake.first][pake.second].pop_back();
}
}
for (int j = 0; j <= t; ++j)
{
vec[i][j] = vec[pake.first][j];
}
}
}
cout << dp[t] << "\n";
return 0;
}
