#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define iii pair<ii, ll>
#define fi first
#define se second
using namespace std;
const int N = (1e5 + 10);
const int S = 2010;
ll n, s, cnt = 0, ans = 0;
ll power[40], dp[S];
ii b[N*40];
iii a[N];
priority_queue <ll> p[S];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("centroid12.inp", "r", stdin);
// freopen("centroid12.out", "w", stdout);
cin >> s >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].fi.fi >> a[i].fi.se >> a[i].se;
power[0] = 1;
for (int i = 1; i <= 29; i++)
power[i] = power[i - 1] * 2;
for (int i = 1; i <= n; i++)
{
ll r = a[i].se, val, w;
for (int j = 0; j <= 29; j++)
{
if (r < power[j])
continue;
r -= power[j];
val = power[j] * a[i].fi.fi, w = power[j] * a[i].fi.se;
if (w <= s)
p[w].push(val);
}
val = r * a[i].fi.fi, w = r * a[i].fi.se;
if (r != 0 && (w <= s))
p[w].push(val);
}
for (int i = 0; i <= s; i++)
{
if (p[i].empty())
continue;
ll len = p[i].size() - s/i;
while (!p[i].empty() && p[i].size() != len)
{
b[++cnt] = {i, p[i].top()};
p[i].pop();
}
}
for (int i = 1; i <= cnt; i++)
for (int j = s; j >= b[i].fi; j--)
dp[j] = max(dp[j], dp[j - b[i].fi] + b[i].se);
for (int i = 0; i <= s; i++)
ans = max(ans, dp[i]);
cout << ans;
return 0;
}
