#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
struct item {
size_t weight = 0;
size_t worth = 0;
size_t count = 0;
};
std::vector<item> filter_items(const std::vector<item>& items, size_t capacity) noexcept {
std::vector<item> filtered;
filtered.reserve(items.size() / 2);
std::unordered_map<size_t, size_t> map;
for (const item& item : items) {
if (map[item.weight] * item.weight > capacity) {
continue;
}
map[item.weight] += item.count;
filtered.push_back(item);
}
return filtered;
}
std::vector<item> prepare_items(std::vector<item>& items, size_t capacity) noexcept {
const auto cmp = [](const item& lhs, const item& rhs) {
return lhs.weight < rhs.weight || (lhs.weight == rhs.weight && lhs.worth > rhs.worth);
};
std::sort(items.begin(), items.end(), cmp);
return filter_items(items, capacity);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
size_t kTypes = 0, capacity = 0;
std::cin >> capacity >> kTypes;
std::vector<item> items(kTypes);
for (size_t i = 0; i < kTypes; ++i) {
size_t weight = 0, worth = 0, count = 0;
std::cin >> worth >> weight >> count;
items[i] = {weight, worth, count};
}
items = prepare_items(items, capacity);
size_t max = 0;
std::vector<size_t> dp(capacity + 1, 0);
for (const auto& item : items) {
size_t cap = capacity;
while (cap-- >= 0) {
size_t count = 1;
while (count <= item.count && count * item.weight <= cap) {
const auto alt = dp[cap - count * item.weight] + count * item.worth;
dp[cap] = std::max(dp[cap], alt);
++count;
}
max = std::max(max, dp[cap]);
if (cap == 0) {
break;
}
}
}
std::cout << max << '\n';
return 0;
}
