#include<iostream>
#include<algorithm>
#include <cmath>
#include<deque>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MANXN = 100000;
int fila[MANXN];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int C;
int n;
cin >> C >> n;
long long v, w, b;
long int dp[2][C+1];
int prev = 0, act = 1;
for ( int c = 0; c <= C; ++c )
dp[prev][c] = 0;
for (int i = 0; i < n; i++) {
cin >> v >> w >> b;
// Iteramos para cada capacidade, assumindo que o resto vai de 0 a w -1
for(int resto=0; resto < w; resto++){
int head=0, tail=-1;
// c%w = Para capacidade c se pegarmos o item de peso w, j vezes, quanto sobra de capacidade
// Como temos até b vezes o item, interamos usando j,
for(int c = resto; c <= C ; c +=w){
//Andamos na fila, atualizando o index da cabeça da fila
//Até o valor da fila for menor que o novo valor - o delta
if(head <= tail && fila[head] < c-b*w) {
head++;
}
while(head <= tail && dp[prev][fila[tail]] - fila[tail]/w*v < dp[prev][c] - c/w*v) {
tail--;
}
fila[++tail] = c;
//para capacidade c qual o max valor possivel
// c - fila[head] -> capacidade atual - o max da fila /w - > quantos items de peso w * valor v unitario
dp[act][c] = dp[prev][fila[head]] + (c-fila[head])/w*v;
}
}
swap( act, prev );
}
cout << dp[prev][C] << endl;
return 0;
}
