#include<iostream>
#include<algorithm>
#include <cmath>
using namespace std;
int main(){
int C;
int n;
cin >> C >> n;
unsigned int V[n];
unsigned int W[n];
unsigned int B[n];
for(int i = 0; i < n; i++){
cin >> V[i] >> W[i] >> B[i];
}
vector<unsigned long long int> NW, NV;
for (int i = 0; i < n; i++ ){
if(B[i] > 1){
int pos = 0;
unsigned long long int x = 1;
// procuramos o bit mais significativo
while( B[i] > x){
pos++;
x = x << pos;
}
// aqui sabemos que (2 ^ pos) >= B[i]
pos--;
// agora 2 ^ pos < B[i], logo (2 ^ pos) - 1 <= B[i]
while ( pos >= 0 ){
unsigned long long int x = 1 << pos;
NW.push_back(x * W[i]);
NV.push_back(x * V[i]);
B[i] -= x;
pos--;
}
if ( B[i] > 0) { // se sobrou um resto
NW.push_back(B[i] * W[i]);
NV.push_back(B[i] * V[i]);
B[i] = 0;
}
} else {
NW.push_back(W[i]);
NV.push_back(V[i]);
B[i] = 0;
}
}
// for(int i = 0; i < NW.size(); i++){
// cout << NW[i] << " " << NV[i] << endl;
// }
unsigned long long 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 = 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;
}
