#include <bits/stdc++.h>
using namespace std;
const long long int maxn = 1e5 + 100, maxs = 2010, inf = 2e12 + 10;
deque <pair <long long int, int>> q[maxs];
int cnt[maxs];
long long int dp[maxn];
void upd(int ind, long long int x, int k)
{
while (q[ind].size() and x > q[ind].back().first)
{
q[ind].pop_back();
}
q[ind].push_back({x, ++cnt[ind]});
if (q[ind].front().second == cnt[ind] - k)
{
q[ind].pop_front();
}
return ;
}
long long int get(int ind)
{
if (q[ind].size())
{
return q[ind].front().first;
}
return -inf;
}
long long int v[maxn], w[maxn], k[maxn];
int main()
{
int s, n;
cin >> s >> n;
for (int i = 1;i <= n;i++)
{
cin >> v[i] >> w[i] >> k[i];
}
for (int i = 0;i < maxs;i++)
{
dp[i] = -inf;
}
dp[s] = 0;
for (int j = 1;j <= n;j++)
{
for (int i = 0;i <= s;i++)
{
cnt[i] = 0;
q[i].clear();
}
for (int i = s;i >= 0;i--)
{
int back = dp[i];
dp[i] = max(dp[i], get(i % w[j]) + v[j] * cnt[i % w[j]]);
upd(i % w[j], back - v[j] * (cnt[i % w[j]]), k[j]);
}
}
long long int ans = 0;
for (int i = 0;i <= s;i++)
{
ans = max(ans, dp[i]);
}
cout << ans;
}
