#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int limitWeight, numItem;
std::cin >> limitWeight >> numItem;
std::vector<std::pair<int, int>> items;
for (int index = 0; index < numItem; index++) {
int value, weight, amount;
std::cin >> value >> weight >> amount;
int power2 = 1;
while (amount >= power2) {
amount -= power2;
items.emplace_back(weight * power2, value * power2);
power2 *= 2;
}
if (amount > 0) {
items.emplace_back(weight * power2, value * power2);
}
}
std::vector<int> maxValue(limitWeight + 1);
for (int index = 0; index < (int)items.size(); index++) {
for (int weight = limitWeight; weight >= 0; weight--) {
if (items[index].first <= weight) {
maxValue[weight] = std::max(maxValue[weight], maxValue[weight - items[index].first] + items[index].second);
}
}
}
std::cout << maxValue[limitWeight];
return 0;
}
