#include<iostream>
#include<algorithm>
#include <cmath>
using namespace std;
const int MAXN = 100000;
const int MAXC = 1000;
int main(){
int C;
int n;
cin >> C >> n;
int V[n];
int W[n];
int B[n];
for (int i = 0; i < n; i++){
cin >> V[i] >> W[i] >> B[i];
}
// long int NW[MAXN];
// long int NV[MAXN];
// long int M = 0;
// // vamos criar os novos itens (pacotes)
// for ( int i = 0; i < n; ++i ){
// int pos = 0;
// // procuramos o bit mais significativo
// while ( (1 << pos) < B[i] )
// pos++;
// // aqui sabemos que (2 ^ pos) >= B[i]
// pos--;
// // agora 2 ^ pos < B[i], logo (2 ^ pos) - 1 <= B[i]
// while ( pos >= 0 ){
// NW[M] = (1 << pos) * W[i];
// NV[M] = (1 << pos) * V[i];
// B[i] -= (1 << pos);
// M++;
// pos--;
// }
// if ( B[i] ){ // se sobrou um resto
// NW[M] = B[i] * W[i];
// NV[M] = B[i] * V[i];
// M++;
// B[i] = 0;
// }
// }
// long long int dp[M + 1][C + 1];
// // caso base : quando nao temos mais itens
// for ( int c = 0; c <= C; ++c )
// dp[M][c] = 0;
// for ( int i = M - 1; i >= 0; --i )
// for ( int c = 0; c <= C; ++c ){
// dp[i][c] = dp[i + 1][c];
// if ( NW[i] <= c )
// dp[i][c] = max( dp[i][c], dp[i + 1][c - NW[i]] + NV[i] );
// }
// caso base : quando nao temos mais itens
int 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 = n - 1; i >= 0; --i ){
for ( int c = 0; c <= C; ++c ){
dp[act][c] = 0; // nao escolhemos nada
for ( int k = 0; W[i]*k <= c && k <= B[i]; ++k ) // testamos cada possibilidade
dp[act][c] = max( dp[act][c], dp[prev][c - k*W[i]] + k*V[i] );
}
swap( act, prev );
}
cout << dp[prev][C] << endl;
return 0;
}
