#include<iostream>
#include<algorithm>
#include <cmath>
using namespace std;
const int MAXN = 300;
const int MAXC = 1000;
int main(){
int C;
int n;
cin >> C >> n;
int V[n];
int W[n];
int B[n];
long int total = n;
for (int i = 0; i < n; i++){
cin >> V[i] >> W[i] >> B[i];
total += log2(B[i]);
}
int NW[total];
int NV[total];
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;
}
}
int dp[total + 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] );
}
cout << dp[0][C] << endl;
return 0;
}
