#include <iostream>
#include <vector>
int main()
{
int32_t count_of_unique_items, max_weight;
std::cin >> max_weight >> count_of_unique_items;
std::vector<int32_t> weights;
std::vector<int32_t> prices;
for (int32_t idx = 0; idx < count_of_unique_items; ++idx)
{
int32_t weight, price, count;
std::cin >> price >> weight >> count;
if (weight > max_weight)
{
continue;
}
count = std::min(count, max_weight / weight);
// "Factorising" count to bits
for (int32_t cur_bit = 1; cur_bit <= count; cur_bit *= 2)
{
weights.push_back(weight * cur_bit);
prices.push_back(price * cur_bit);
count -= cur_bit;
}
// Remained bits
if (count > 0)
{
weights.push_back(weight * count);
prices.push_back(price * count);
}
}
size_t count_of_items_new = weights.size();
// We just need an answer, so we dont need to store all data
std::vector<std::vector<int64_t>> dp(2,
std::vector<int64_t>(max_weight + 1, 0));
for (size_t j = 1; j <= count_of_items_new; ++j)
{
for (int32_t weight = 1; weight <= max_weight; ++weight)
{
if (weights[j - 1] <= weight)
{
dp[1][weight] = std::max(dp[0][weight],
dp[0][weight - weights[j - 1]] + prices[j - 1]);
}
else
{
dp[1][weight] = dp[0][weight];
}
}
for (int32_t weight = 0; weight <= max_weight; ++weight)
{
dp[0][weight] = dp[1][weight];
}
}
int64_t mmax = 0;
for (int32_t idx = max_weight; idx >= 0; --idx)
{
mmax = std::max(mmax, dp[1][idx]);
}
std::cout << mmax << std::endl;
return 0;
// If we want to print taken elements
// std::vector<std::vector<int64_t>> dp(count_of_items_new + 1,
// std::vector<int64_t>(max_weight + 1, 0));
// for (size_t j = 1; j <= count_of_items_new; ++j)
// {
// for (int32_t weight = 1; weight <= max_weight; ++weight)
// {
// if (weights[j - 1] <= weight)
// {
// dp[j][weight] = std::max(dp[j - 1][weight],
// dp[j - 1][weight - weights[j - 1]] + prices[j - 1]);
// }
// else
// {
// dp[j][weight] = dp[j - 1][weight];
// }
// }
// }
// for (int32_t idx = max_weight; idx >= 0; --idx)
// {
// if (dp[count_of_items_new][idx])
// {
// std::cout << dp[count_of_items_new][idx] << std::endl;
// return 0;
// }
// }
// std::cout << 0 << std::endl;
// return 0;
}
