#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
struct item {
size_t weight = 0;
size_t value = 0;
size_t count = 0;
};
size_t dp[100001];
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::vector<item> items(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;
items[i] = {weight, value, count};
}
const auto cmp = [](const item& lhs, const item& rhs) {
if (lhs.weight == rhs.weight) {
return lhs.value > rhs.value;
}
return lhs.weight < rhs.weight;
};
std::sort(items.begin(), items.end(), cmp);
size_t max = 0;
for (const auto& item : items) {
for (size_t cap = capacity; cap > 0; --cap) {
size_t limit = std::min(item.count, cap / item.weight);
for (size_t count = 1; count <= limit; ++count) {
const auto alt = dp[cap - count * item.weight] + count * item.value;
dp[cap] = std::max(dp[cap], alt);
}
max = std::max(max, dp[cap]);
}
}
std::cout << max << '\n';
return 0;
}
