#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct hw
{
ll val, w, k;
};
void solve()
{
ll s, n;
cin >> s >> n;
vector<hw> v(n);
for (auto &i : v)
{
cin >> i.val >> i.w >> i.k;
}
if (n == 1)
{
if (s < v[0].w)
{
cout << 0 << '\n';
return;
}
ll cal = s / v[0].w;
if (cal >= v[0].k)
{
cout << v[0].val * v[0].k << '\n';
}
else if (cal < v[0].k)
{
cout << v[0].val * cal << '\n';
}
}
else
{
vector<ll> dp(s + 1, 0);
for (auto &i : v)
{
for (int j = s; j >= 1; j--)
{
for (int l = 1; l <= i.k; l++)
{
if (i.w * l <= j)
{
dp[j] = max(dp[j], i.val * l + dp[j - i.w * l]);
}
}
}
}
cout << dp[s] << '\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
