#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Structura pentru a retine obiectele grupate pe greutate
struct Item {
int v, k;
};
// Sortam descrescator dupa valoare
bool compareItems(const Item& a, const Item& b) {
return a.v > b.v;
}
vector<Item> items_by_weight[2001];
long long dp[2001];
int main() {
// Optimizare I/O obligatorie
ios::sync_with_stdio(false);
cin.tie(NULL);
int S, n;
cin >> S >> n;
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
if (w <= S) {
items_by_weight[w].push_back({v, k});
}
}
for (int w = 1; w <= S; w++) {
if (items_by_weight[w].empty()) continue;
// Sortam obiectele de greutate w pentru a le lua pe cele mai valoroase
sort(items_by_weight[w].begin(), items_by_weight[w].end(), compareItems);
int total_needed = S / w; // Nu putem lua mai mult de atat
int taken = 0;
for (auto& item : items_by_weight[w]) {
int can_take = min(item.k, total_needed - taken);
if (can_take <= 0) break;
taken += can_take;
// Aici intervine "Magia": Descompunerea binara doar pe 'can_take'
// Asta previne adaugarea a mii de obiecte individuale in DP
for (int p = 1; p <= can_take; p <<= 1) {
int val_p = p * item.v;
int weight_p = p * w;
for (int j = S; j >= weight_p; j--) {
dp[j] = max(dp[j], dp[j - weight_p] + val_p);
}
can_take -= p;
}
if (can_take > 0) {
int val_rem = can_take * item.v;
int weight_rem = can_take * w;
for (int j = S; j >= weight_rem; j--) {
dp[j] = max(dp[j], dp[j - weight_rem] + val_rem);
}
}
}
}
cout << dp[S] << endl;
return 0;
}
