#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e3 + 5, mod = 1e9 + 7;
int n, m;
int dp[maxn];
vector<array<int, 2>> a;
vector<pair<int,int>> b[maxn];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
cin >> m >> n;
for (int i = 1; i <= n; i++)
{
int val, w, num;
cin >> val >> w >> num;
b[w].emplace_back(val, num);
}
for (int i = 1; i <= m; i++)
{
int lim = m;
sort(b[i].begin(), b[i].end(), greater<>());
for (auto p : b[i])
{
int val, num;
tie(val, num) = p;
num = min(num, lim / i);
int cur = 1;
while (num >= cur)
{
a.push_back({val * cur, i * cur});
num -= cur;
lim -= cur;
cur *= 2;
}
if (num)
a.push_back({val * num, i * num}),
lim -= num;
}
}
memset(dp, -0x3f, sizeof dp);
int oo = dp[0];
dp[0] = 0;
for (auto p : a)
{
int u = p[0], v = p[1];
for (int i = m; i >= v; i--) if (dp[i - v] != oo)
dp[i] = max(dp[i], dp[i - v] + u);
}
cout << *max_element(dp, dp + m + 1);
}
