#include <bits/stdc++.h>
using namespace std;
typedef struct item item;
struct item
{
uint64_t w;
uint64_t v;
uint64_t k;
};
bool item_cmp(item a, item b)
{
if (a.w < b.w)
return 1;
else if (b.w < a.w)
return 0;
else
{
if (a.v < b.v)
return 1;
else
return 0;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
uint64_t s, n;
cin >> s >> n;
vector<item> items(n);
for (size_t i = 0; i < n; i++)
{
item &x = items[i];
cin >> x.v >> x.w >> x.k;
}
sort(items.begin(), items.end(), item_cmp);
vector<uint64_t> cost;
vector<uint64_t> value;
auto it = --items.end();
for (uint64_t w = s; w > 0; w--)
{
uint64_t incl = s / w + 1;
while (incl && it != --items.begin() && it->w == w)
{
cost.push_back(it->w);
value.push_back(it->v);
incl--;
if (it->k > 1)
it->k--;
else
it--;
}
}
vector<vector<uint64_t>> dp(cost.size(), vector<uint64_t>(s + 1, 0));
for (uint64_t i = cost[0]; i < s + 1; i++)
dp[0][i] = value[0];
for (size_t i = 1; i < cost.size(); i++)
{
for (size_t j = 1; j < s + 1; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= cost[i] && dp[i - 1][j - cost[i]] + value[i] > dp[i][j])
dp[i][j] = dp[i - 1][j - cost[i]] + value[i];
}
}
cout << dp[cost.size() - 1][s] << '\n';
}
