#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct item {
long long valor;
long long peso;
long long qtd;
item() {}
item(long long v, long long p, long long q) {
valor = v;
peso = p;
qtd = q;
}
};
bool cmp(const item &A, const item &B) { return A.valor > B.valor; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int C;
int n;
cin >> C >> n;
// entre todos com peso w, so precisamos considerar os mais valiosos C / w
// elementos
long long v, w, b;
vector<long long> Limite(C + 1, 0);
for (int i = 1; i <= C; ++i)
Limite[i] =
C / i; // esse eh o num. maximo de itens que podemos usar de peso i
vector<item> I;
for (int i = 0; i < n; i++) {
cin >> v >> w >> b;
if (w <= C)
I.push_back(item(v, w, b));
}
// ordenamos para considerar os itens de maior valor primeiro
sort(I.begin(), I.end(), cmp);
// agora vou criar outro vetor de itens so com os que vou considerar
vector<item> ListaItens;
for (int i = 0; i < (int)I.size(); ++i) {
v = I[i].valor;
w = I[i].peso;
b = I[i].qtd;
if (Limite[w] == 0)
continue; // nao precisa mais considerar esse peso
// ajustamos a quantidade
b = min(b, Limite[w]);
ListaItens.push_back(item(v, w, b));
Limite[w] -= b; // reduzimos o limite
}
n = (int)ListaItens.size();
// agora fazemos a programacao dinamica da mochila limitada
/*
completar
*/
vector<long long> NW, NV;
for (int i = 0; i < n; i++) {
int x = 1;
while (ListaItens[i].qtd > x) {
ListaItens[i].qtd -= x;
NW.push_back(x * ListaItens[i].peso);
NV.push_back(x * ListaItens[i].valor);
x = x << 1;
}
NW.push_back(ListaItens[i].peso * ListaItens[i].qtd);
NV.push_back(ListaItens[i].valor * ListaItens[i].qtd);
}
long long dp[2][C + 1];
int prev = 0, act = 1;
// caso base : quando nao temos mais itens
for (int c = 0; c <= C; c++)
dp[prev][c] = 0;
for (int i = NW.size() - 1; i >= 0; i--) {
for (int c = 0; c <= C; c++) {
dp[act][c] = dp[prev][c];
if (NW[i] <= c) {
dp[act][c] = max(dp[act][c], dp[prev][c - NW[i]] + NV[i]);
}
}
swap(act, prev);
}
cout << dp[prev][C] << endl;
return 0;
}
