#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
#define pii pair<int,int>
int s, n;
int pre[MAXN][MAXN];
int dp[MAXN][MAXN];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> s >> n;
vector<vector<pii>> a(s + 1);
for (int i = 1; i <= n; i++)
{
int v, w, k;
cin >> v >> w >> k;
a[w].push_back({v, k});
}
for (int i = 1; i <= s; i++)
{
sort(a[i].rbegin(), a[i].rend());
}
for (int i = 1; i <= s; i++)
{
if (a.empty())
{
continue;
}
int cnt = 1;
int typ = 0;
int sz = a[i].size();
int rem = 1;
while(cnt <= s and typ < sz)
{
pre[i][cnt] = pre[i][cnt - 1] + a[i][typ].first;
++cnt;
++rem;
if (rem > a[i][typ].second)
{
rem = 1;
++typ;
}
}
}
for (int i = 1; i <= s; i++)
{
for (int j = 1; j <= s; j++)
{
dp[i][j] = dp[i - 1][j];
}
for (int j = 1; j <= s; j++)
{
for (int k = 1; k * i <= j; k++)
{
dp[i][j] = max(dp[i][j], dp[i - 1][j - i * k] + pre[i][k]);
}
}
}
cout << dp[s][s];
}
