#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) {
// 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 valor da DP usando o melhor da janela
if (!dq.empty()) {
dp[j] = max(dp[j], dq.front().first + (j / w) * v);
}
// Prepara o valor atual para ser inserido na fila
ll val = dp[j] - (j / w) * v;
// Mantém a fila monotônica (decrescente), removendo piores elementos do final
while (!dq.empty() && dq.back().first <= val) {
dq.pop_back();
}
dq.push_back({val, j});
}
}
}
}
cout << dp[S] << endl;
return 0;
}
