#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, x;
cin >> x >> n;
vector<int> price(n + 1), page(n + 1), num(n + 1);
for (int i = 1; i <= n; i++) cin >> page[i] >> price[i] >> num[i];
vector dp(2, vector<int>(x + 1));
for (int i = 1; i <= n; i++)
{
for (int rem = 0; rem < price[i]; rem++)
{
deque<pair<int, int>> ms;
auto add = [&] (int idx, int val) -> void
{
while (!ms.empty() && ms.back().second < val) ms.pop_back();
ms.emplace_back(idx, val);
};
auto del = [&] (int idx) -> void
{
if (!ms.empty() && ms.front().first == idx) ms.pop_front();
};
auto maximum = [&] () -> int
{
return ms.front().second;
};
for (int j = rem, cnt = 0; j <= x; j += price[i], cnt++)
{
add(j, dp[(i + 1) % 2][j] - cnt * page[i]);
int outdatedIndex = j - (num[i] + 1) * price[i];
if (outdatedIndex >= 0)
{
del(outdatedIndex);
}
dp[i % 2][j] = maximum() + cnt * page[i];
}
}
}
cout << dp[n % 2][x] << '\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]
