#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;
ll power[N], dp[S];
ii b[N];
iii a[N];
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 <= 11; i++)
power[i] = power[i - 1] * 2;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= 11; j++)
{
if (power[j] > a[i].se)
continue;
ll val = a[i].fi.fi * power[j];
ll w = a[i].fi.se * power[j];
if (w > s)
continue;
b[++cnt] = {w, val};
}
}
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);
cout << dp[s];
return 0;
}
