#include <bits/stdc++.h>
using namespace std;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int s, n;
cin >> s >> n;
vector<pair<int, pair<int, int>>> vpp;
for (int i = 0; i < n; i++)
{
int x, y, z;
cin >> x >> y >> z;
vpp.push_back({x, {y, z}});
}
if (n == 1)
{
int d = s / vpp[0].first;
cout << min(vpp[0].second.second, d) * (vpp[0].second.first);
return 0;
}
vector<pair<int, int>> vp;
for (auto it : vpp)
{
int reward = it.first;
int cost = it.second.first;
int quantity = it.second.second;
int cur = 1;
while (quantity > 0)
{
int take = min(cur, quantity);
vp.push_back({cost * take, reward * take});
quantity -= take;
cur *= 2;
}
}
vector<int> dp(s + 1, 0);
for (auto it : vp)
{
int cost = it.first;
int reward = it.second;
for (int j = s; j >= cost; j--)
{
dp[j] = max(dp[j], dp[j - cost] + reward);
}
}
cout << *max_element(dp.begin(), dp.end());
return 0;
}
