#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {
int weight_limit, num_types;
cin >> weight_limit >> num_types;
/*
* Group items by their weight.
* For each weight w:
* we store (value, amount)
*/
map<int, vector<pair<int, int>>> items_by_weight;
for (int i = 0; i < num_types; i++) {
int value, weight, amount;
cin >> value >> weight >> amount;
if (weight <= weight_limit && amount > 0) {
items_by_weight[weight].push_back({value, amount});
}
}
/*
* dp[i][j] = maximum value achievable
* using the first i distinct weights
* with total weight exactly j
*
* i goes over weight groups, not individual items
*/
int W = items_by_weight.size();
vector<vector<long long>> dp(
W + 1, vector<long long>(weight_limit + 1, -1e18)
);
dp[0][0] = 0; // base case
int group_index = 1;
for (auto &[weight, items] : items_by_weight) {
// Sort items of same weight by value (descending)
sort(items.begin(), items.end(), greater<>());
for (int used_weight = 0; used_weight <= weight_limit; used_weight++) {
// Option 1: take nothing from this weight group
dp[group_index][used_weight] =
dp[group_index - 1][used_weight];
long long gained_value = 0;
int copies_taken = 0;
int item_index = 0;
int taken_from_item = 0;
/*
* Try taking 1, 2, 3, ... copies of this weight
* while staying within weight limit
*/
while ((copies_taken + 1) * weight <= used_weight &&
item_index < items.size()) {
copies_taken++;
gained_value += items[item_index].first;
taken_from_item++;
if (dp[group_index - 1][used_weight - copies_taken * weight] >= 0) {
dp[group_index][used_weight] = max(
dp[group_index][used_weight],
dp[group_index - 1][used_weight - copies_taken * weight]
+ gained_value
);
}
// Move to next item if current one is exhausted
if (taken_from_item == items[item_index].second) {
taken_from_item = 0;
item_index++;
}
}
}
group_index++;
}
cout << *max_element(dp[W].begin(), dp[W].end()) << endl;
}
