#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);
}
}
int binSearch(int v) {
int len = (int) ordered_values.size();
int low = 0;
int high = len - 1;
while( low <= high) {
int mid = low + ((high - low) / 2);
if (ordered_values[mid] < v) low = mid + 1;
else if (ordered_values[mid] > v) high = mid - 1;
else return mid + 1;
}
if (high < 0)
return 0;
else
if (low > (len - 1))
return len;
else
return (low < high) ? low + 1 : high + 1;
}
void add_items(int v, int k) {
int num_items = min(k, max_items);
int ins_ind = 0;
// for (; ins_ind < (int) ordered_values.size() && ordered_values[ins_ind] < v; ins_ind++) {} // TODO: Bin. Search
ins_ind = binSearch(v - 1);
// num_items = min(num_items, max_items - ins_ind);
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;
}
