#include<iostream>
#include<algorithm>
#include <cmath>
using namespace std;
#define NMAX 500000
int main(){
int C;
int n;
cin >> C >> n;
long long v, w, b;
long long NW[NMAX], NV[NMAX];
long long idx = 0;
for(int i = 0; i < n; i++){
int x = 1;
cin >> v >> w >> b;
while(b > x){
b -= x;
NW[idx] = (x * w);
NV[idx] = (x * v);
idx++;
x = x << 1;
}
NW[idx] = (w * b);
NV[idx] = (v * b);
idx++;
}
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 = idx - 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;
}
