#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
int main() { _
int S, N;
cin >> S >> N;
vector<ll> dp(S + 1, 0);
for (int i = 0; i < N; i++) {
ll v, w, k; // Valor, Peso, Quantidade
cin >> v >> w >> k;
// Se o item é efetivamente ilimitado, usamos a DP O(S) padrão.
if (k * w >= S) {
for (int j = w; j <= S; j++) {
dp[j] = max(dp[j], dp[j - w] + v);
}
} else {
// Se o item é limitado, usamos a otimização O(S) com fila monotônica.
for (int rem = 0; rem < w; rem++) {
deque<pair<ll, ll>> dq;
for (int j = rem; j <= S; j += w) {
// --- CORREÇÃO ESTÁ AQUI ---
// O valor que será usado para a fila deve ser baseado no estado
// de dp[j] ANTES de qualquer modificação nesta iteração.
ll val_para_fila = dp[j] - (j / w) * v;
// Remove da frente da fila os estados que estão fora da "janela" de k itens.
if (!dq.empty() && dq.front().second < j - k * w) {
dq.pop_front();
}
// Calcula o NOVO valor de dp[j] usando o melhor da janela (que contém valores antigos).
if (!dq.empty()) {
dp[j] = max(dp[j], dq.front().first + (j / w) * v);
}
// Mantém a fila monotônica, removendo piores elementos do final.
while (!dq.empty() && dq.back().first <= val_para_fila) {
dq.pop_back();
}
// Insere o valor (baseado no estado antigo) na fila para futuras iterações.
dq.push_back({val_para_fila, j});
}
}
}
}
cout << dp[S] << endl;
return 0;
}
