#include <iostream>
#include <vector>
#include <map>
using namespace std;
struct Weight_Group {
int weight, max_items;
vector<int> ordered_values;
Weight_Group() : weight(0), max_items(2000) {}
Weight_Group(int w, int v, int k, int max_weight) : weight(w), max_items(max_weight / w) {
int num_items = min(k, max_items);
for (int i = 0; i < num_items; i++) {
ordered_values.push_back(v);
}
}
void add_items(int v, int k) {
int num_items = min(k, max_items);
for (int i = 0; i < num_items; i++) {
ordered_values.push_back(v);
}
// int ins_ind = 0;
// for (; ins_ind < (int) ordered_values.size() && ordered_values[ins_ind] < v; ins_ind++) {} // TODO: Bin. Search
// for (int i = 0; i < num_items; i++) {
// ordered_values.insert(ordered_values.begin() + ins_ind, v);
// }
// while ((int) ordered_values.size() > max_items) {
// ordered_values.erase(ordered_values.begin());
// }
}
};
int main() {
int max_weight, num_items;
cin >> max_weight >> num_items;
bool map_key_exists[2001] = {0};
Weight_Group map_values[2001];
for (int i = 0; i < num_items; i++) {
int v, w, k;
cin >> v >> w >> k;
if (map_key_exists[w]) {
map_values[w].add_items(v, k);
} else {
map_values[w] = Weight_Group(w, v, k, max_weight);
map_key_exists[w] = true;
}
}
int max_val_for_weight[2001] = {0};
for (int i = 0; i < max_weight; i++) {
if (map_key_exists[i]) {
for (int v : map_values[i].ordered_values) {
for (int k = max_weight; k >= 0; k--) {
if (k - i >= 0) {
max_val_for_weight[k] = max(max_val_for_weight[k], max_val_for_weight[k - i] + v);
}
}
}
}
}
cout << max_val_for_weight[max_weight] << endl;
}
