#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
typedef long double ld;
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(x) x.begin(), x.end()
#define pll pair<ll, ll>
#define vec vector
#define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const ll mod = 1e9 + 7;
ld fpow(ll a, ll b, ll m = -1)
{
if (m != -1)
a %= m;
ll res = 1;
while (b > 0)
{
if (b % 2 == 1)
{
if (m != -1)
res = res * a % m;
else
{
res *= a;
}
}
a = a * a;
if (m != -1)
{
a %= m;
}
b /= 2;
}
return res;
}
int main()
{
// fast;
// freopen("pails.in", "r", stdin);
// freopen("pails.out", "w", stdout);
ll t = 1;
// cin >> t;
while (t--)
{
ll n, s;
cin >> s >> n;
vec<vec<array<ll, 2>>> v(s + 1);
for (int i = 0; i < n; i++)
{
ll a, b, c;
cin >> a >> b >> c;
v[b].push_back({a, c});
}
for (int i = 0; i <= s; i++)
{
sort(all(v[i]), greater<array<ll, 2>>());
}
vec<vec<ll>> dp(s + 1, vec<ll>(s + 1));
for (int i = 0; i <= s; i++)
{
if(i)
dp[i] = dp[i - 1];
ll cur = 0, cur2 = 0;
for (int j = 0; j < v[i].size(); j++)
{
for (int ii = 0; ii < v[i][j][1]; ii++)
{
cur += v[i][j][0], cur2 += i;
if (cur2 > s)
{
break;
}
for (int k = cur2; k <= s; k++)
{
dp[i][k] = max(dp[i][k], dp[i - 1][k - cur2] + cur);
}
}
if (cur2 > s)
{
break;
}
}
}
ll mx = 0;
for (int i = 0; i <= s; i++)
{
mx = max(mx, dp[s][i]);
}
cout << mx << '\n';
end:;
}
return 0;
}
