#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXC = 2005;
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;
}
long long dp[2][MAXC];
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(n);
for ( int i = 0; i < n; i++ ){
cin >> v >> w >> b;
I[i] = item(v, w, b);
}
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 < n; ++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
}
// agora fazemos a programacao dinamica da mochila limitada
int ant = 0, act = 1;
for ( int j = 0; j <= C; ++j )
dp[ant][j] = 0;
for ( int i = n - 1; i >= 0; --i ){
w = ListaItens[i].peso;
v = ListaItens[i].valor;
b = ListaItens[i].qtd;
for ( int j = 1; j <= C; ++j ){
dp[act][j] = dp[ant][j]; // nao usamos o item
for ( int k = 1; k <= b && k * w <= j; k++ )
dp[act][j] = max( dp[act][j], dp[ant][j - k*w] + v*k );
}
swap( ant, act );
}
cout << dp[ant][C] << endl;
return 0;
}
