#include <algorithm>
#include <iostream>
#include <limits>
#include <unordered_map>
#include <vector>
struct item {
size_t weight = 0;
size_t value = 0;
size_t count = 0;
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
size_t amount_of_types = 0, capacity = 0;
std::cin >> capacity >> amount_of_types;
std::unordered_map<size_t, std::vector<item>> buckets(amount_of_types);
for (size_t i = 0; i < amount_of_types; ++i) {
size_t weight = 0, value = 0, count = 0;
std::cin >> value >> weight >> count;
if (weight <= capacity) {
buckets[weight].push_back({weight, value, count});
}
}
const auto cmp_most_valuable = [](const item& lhs, const item& rhs) {
return lhs.value > rhs.value || (lhs.value == rhs.value && lhs.count > rhs.count);
};
std::vector<size_t> dp(capacity + 1, 0);
for (auto& it : buckets) {
const size_t weight = it.first;
auto& bucket = it.second;
std::sort(bucket.begin(), bucket.end(), cmp_most_valuable);
size_t index = 0;
for (size_t count = 1; count * weight <= capacity && index < bucket.size(); ++count) {
for (size_t cap = capacity; cap >= weight; --cap) {
dp[cap] = std::max(dp[cap], dp[cap - weight] + bucket[index].value);
}
--bucket[index].count;
if (bucket[index].count == 0) {
++index;
}
}
}
std::cout << dp[capacity] << '\n';
return 0;
}
