#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <random>
#ifdef _MSC_VER
# include <intrin.h>
# define __builtin_popcountll __popcnt
#endif
//#include <atcoder/all>
//using namespace atcoder;
//typedef modint998244353 mint;
using namespace std;
typedef long long int lld;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<lld, lld> pll;
typedef vector<int> vi;
typedef vector<lld> vl;
typedef vector<ld> vld;
typedef vector<char> vch;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vivi;
typedef vector<vl> vlvl;
typedef vector<vch> vcvc;
typedef vector<vb> vbvb;
typedef vector<vs> vsvs;
const lld mod = 1000000000000;
const lld inf = 1LL << 56;
const int nom = 200000;
typedef struct node
{
lld val;
int wei;
} node;
int cmp(const node& a, const node& b)
{
return a.wei < b.wei;
}
int main()
{
cin.tie(NULL), cout.tie(NULL);
ios::sync_with_stdio(false);
int s, n, idx, mn, gt;
lld tp, tp2, tp3, now, tp4, tp5;
cin >> s >> n;
vlvl vals(s + 1);
vector<node> good;
for (int i = 0; i < n; ++i)
{
cin >> tp >> tp2 >> tp3;
now = tp3, gt = 1;
tp4 = tp, tp5 = tp2;
for (int j = 0; j < 13; ++j)
{
if (gt <= now && tp5 <= s)
{
vals[tp5].push_back(tp4);
now -= gt;
}
gt *= 2, tp4 *= 2, tp5 *= 2;
}
if (now && tp2 * now <= s)
vals[tp2 * now].push_back(tp * now);
}
for (int i = 1; i <= s; ++i)
sort(vals[i].begin(), vals[i].end(), greater<lld>());
for (int i = 1; i <= s; ++i)
{
mn = min((int)vals[i].size(), s / i);
for (int j = 0; j < mn; ++j)
good.push_back({ vals[i][j], i });
}
sort(good.begin(), good.end(), cmp);
vl dp(s + 1, -1), next(s + 1);
mn = s;
idx = (int)good.size() - 1;
while (idx >= 0 && good[idx].wei > s / 2)
{
mn = good[idx].wei;
if (good[idx].wei <= s)
dp[good[idx].wei] = max(dp[good[idx].wei], good[idx].val);
idx--;
}
dp[0] = 0;
for (int i = idx; i >= 0; --i)
{
for (int j = mn; j <= s; ++j)
next[j] = -1;
for (int j = mn; j <= s; ++j)
{
if (dp[j] == -1)
continue;
if (j + good[i].wei <= s)
next[j + good[i].wei] = max(next[j + good[i].wei], dp[j] + good[i].val);
next[j] = max(next[j], dp[j]);
}
for (int j = mn; j <= s; ++j)
dp[j] = next[j];
if (good[i].wei <= s)
dp[good[i].wei] = max(dp[good[i].wei], good[i].val);
mn = good[i].wei;
}
tp = 0;
for (int i = 0; i <= s; ++i)
tp = max(tp, dp[i]);
cout << tp;
cout << '\n';
return 0;
}
