#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
void solve()
{
int s, n, dp[2005], v, w, k;
cin >> s >> n;
for (int i = 1; i <= n; i++)
{
cin >> v >> w >> k;
for (int r = 0; r < w; r++)
{
int dq[2005][2], head = 0, tail = 0, q = 0;
for (int j = r; j <= s; j += w)
{
int mn = min(q, k);
while (tail - head > 0 and dq[head][1] < q - mn)
{
head++;
}
while (tail - head > 0 and dq[tail - 1][0] <= dp[j] - q * v)
{
tail--;
}
dq[tail][0] = dp[j] - q * v;
dq[tail][1] = q;
tail++;
dp[j] = dq[head][0] + q * v;
q++;
}
}
}
cout << dp[s] << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t = 1;
// cin >> t;
for (ll i = 1; i <= t; i++)
{
solve();
}
}
