#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Use long long for values to avoid overflow
typedef long long ll;
// A simple structure to represent an item in our final DP list
struct FinalItem {
ll value;
ll weight;
};
// This is the comparison function.
// It tells the sort algorithm: "Put the item with the higher value first."
bool compareByValue(const pair<int, int>& a, const pair<int, int>& b) {
return a.first > b.first;
}
int main() {
// Speeds up input and output
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int S, N;
if (!(cin >> S >> N)) return 0;
// weight_groups[w] stores a list of {value, quantity} for weight 'w'
vector<vector<pair<int, int>>> weight_groups(S + 1);
for (int i = 0; i < N; i++) {
int v, w, k;
cin >> v >> w >> k;
if (w <= S) {
weight_groups[w].push_back({v, k});
}
}
vector<FinalItem> items_to_process;
// Process each weight from 1 to S
for (int w = 1; w <= S; w++) {
if (weight_groups[w].empty()) continue;
// Use our custom function to sort items of this weight by value
sort(weight_groups[w].begin(), weight_groups[w].end(), compareByValue);
// We only need enough items to fill the total capacity S.
// If weight is w, we can fit at most S/w items.
int total_needed = S / w;
int collected_so_far = 0;
for (int i = 0; i < weight_groups[w].size(); i++) {
int val = weight_groups[w][i].first;
int qty = weight_groups[w][i].second;
// How many can we take from this specific item type?
int can_take = min(qty, total_needed - collected_so_far);
if (can_take <= 0) break; // We have enough items of this weight
collected_so_far += can_take;
// Binary Splitting: instead of adding 'can_take' items one by one,
// we group them into powers of 2 (1, 2, 4, 8...).
// This is a standard trick to solve Bounded Knapsack efficiently.
for (int p = 1; can_take > 0; p <<= 1) {
int batch_size = min(p, can_take);
items_to_process.push_back({(ll)batch_size * val, (ll)batch_size * w});
can_take -= batch_size;
}
}
}
// Standard 0/1 Knapsack DP
// dp[j] = maximum value we can get with total weight j
vector<ll> dp(S + 1, 0);
for (int i = 0; i < items_to_process.size(); i++) {
ll item_v = items_to_process[i].value;
ll item_w = items_to_process[i].weight;
// Standard Knapsack loop: iterate backwards to ensure each
// split item is used only once.
for (int j = S; j >= item_w; j--) {
if (dp[j - item_w] + item_v > dp[j]) {
dp[j] = dp[j - item_w] + item_v;
}
}
}
cout << dp[S] << endl;
return 0;
}
