#include<iostream>
#include<algorithm>
#include <cmath>
#include<deque>
using namespace std;
class MaxQueue {
private:
int ti; // tempo do item na frente da fila
int tf; // tempo do item no fim da fila
int delta; // guarda o total das somas feitas aos elementos
deque< pair<int,int> > Q; // elementos da fila armazenados como tuplas (valor, tempo)
public:
MaxQueue(){
// inicializacao
delta = ti = tf = 0;
Q.clear();
}
void push( int x ){
int x_delta = x - delta;
while ( !Q.empty() && Q.back().first <= x_delta )
Q.pop_back();
Q.push_back( pair<int,int>( x_delta, tf++ ) );
}
void pop(){
if ( Q.empty() ){
return;
}
if ( ti == Q.front().second ) // se o elemento na frente eh realmente a frente na estrutura
Q.pop_front();
ti++;
}
int max(){
if ( Q.empty() ){
return -1;
}
return Q.front().first + delta;
}
void addAll( int d ){
if ( !Q.empty() )
delta += d;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int C;
int n;
cin >> C >> n;
long long v, w, b;
vector<long long> dp(C + 1, 0);
for (int i = 0; i < n; i++) {
cin >> v >> w >> b;
//para cada novo item
for (int sobra = 0; sobra < w; sobra++) {
MaxQueue mq;
// 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,
//Iteramos para cada capacidade, assumindo que a sobra vai de 0 a w -1
for (int j = 0, c = sobra; c <= C; j++, c += w) {
mq.push(dp[c]);
//Se ultrapassamos o limite de itens removemos da fila
if (j - b > 0)
mq.pop();
dp[c] = mq.max();
//Adicionamos v a todos os item da fila
//Pois dp[c] = max(dp[c], dp[c-w] + v, dp[c-2w]+2v....dp[c-2n]+2vn)
//Logo adicionamos o valor v a cada loop, ou seja os elementos mais antigos vão ter n*v adicionado a eles
mq.addAll(v);
}
}
}
cout << dp[C] << endl;
return 0;
}
