#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
// Folosim un vector de vectori pentru a grupa valorile dupa greutate
// Greutatea maxima S este 2000
vector<int> valori_per_greutate[2001];
long long dp[2001];
int main() {
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;
// Daca obiectul e mai greu decat rucsacul, il ignoram
if (w <= S) {
// Adaugam valoarea de k ori (dar nu mai mult de cat incape in rucsac)
int limita = min(k, S / w);
for (int j = 0; j < limita; j++) {
valori_per_greutate[w].push_back(v);
}
}
}
// Initializam DP cu 0
// dp[j] = valoarea maxima pentru capacitatea j
for (int w = 1; w <= S; w++) {
if (valori_per_greutate[w].empty()) continue;
// Sortam valorile descrescator pentru greutatea curenta
sort(valori_per_greutate[w].begin(), valori_per_greutate[w].end(), greater<int>());
// Luam doar cele mai bune obiecte (limitare suplimentara S/w)
int limita = S / w;
int nr_obiecte = min((int)valori_per_greutate[w].size(), limita);
for (int i = 0; i < nr_obiecte; i++) {
int v = valori_per_greutate[w][i];
// Rucsac 0/1 clasic (parcurgere inversa)
for (int j = S; j >= w; j--) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
}
cout << dp[S] << endl;
return 0;
}
