#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
int limit, type_num;
cin >> limit >> type_num;
vector<vector<pair<int, int>>> by_weight(limit + 1);
for (int t = 0; t < type_num; t++) {
int value, weight, amt;
cin >> value >> weight >> amt;
if (weight <= limit && amt > 0) {
by_weight[weight].push_back({value, amt});
}
}
vector<long long> best(limit + 1, INT32_MIN);
best[0] = 0;
for (int w = 1; w <= limit; w++) {
if (!by_weight[w].empty()) {
sort(by_weight[w].rbegin(), by_weight[w].rend());
for (auto &item : by_weight[w]) {
int value = item.first;
int count = item.second;
for (int j = limit; j >= w; j--) {
int copies = 0;
long long profit = 0;
while (copies < count && j >= (copies + 1) * w) {
copies++;
profit += value;
if (best[j - copies * w] != INT32_MIN) {
best[j] = max(best[j], best[j - copies * w] + profit);
}
}
}
}
}
}
long long max_value = *max_element(best.begin(), best.end());
cout << max_value << endl;
return 0;
}
