#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
void solve()
{
int n, s;
cin >> s >> n;
vector<int> price(n + 1), page(n + 1), num(n + 1);
vector mp(s + 1, vector<pair<int,int>>{});
for (int i = 1; i <= n; i++)
{
cin >> page[i] >> price[i] >> num[i];
mp[price[i]].emplace_back(page[i], num[i]);
}
vector<int> newPrice;
vector<int> newPage;
for (int i = 1; i <= s; i++)
{
sort(mp[i].rbegin(), mp[i].rend());
int cnt = 1;
for (auto [a, b] : mp[i])
{
for (int it = 1; it <= b; it++)
{
newPrice.push_back(i);
newPage.push_back(a);
++cnt;
if (cnt == (s + i - 1) / i + 1) break;
}
if (cnt == (s + i - 1) / i + 1) break;
}
}
int m = newPrice.size();
newPrice.insert(newPrice.begin(), 0);
newPage.insert(newPage.begin(), 0);
vector dp(m + 1, vector<int>(s + 1, 0));
for (int i = 1; i <= m; i++)
{
for (int j = 0; j <= s; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= newPrice[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - newPrice[i]] + newPage[i]);
}
}
cout << dp[m][s] << '\n';
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tc = 1;
// cin >> tc;
while (tc--) solve();
return 0;
}
// dp[i][j] = maximum number of pages i can buy having bought considering first i distinct books and with j money
// dp[i][j] = dp[i - 1][j - (0..k[i]) * h[i]] + (0..k[i]) * s[i]
// dp[i - 1][ j - (0...k[i]) * h[i] ] + (0...k[i]) * s[i]
