#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
const int MAX_N = 100000;
const int MAX_S = 2000;
int S;
int N;
int V[MAX_N];
int W[MAX_N];
int K[MAX_N];
int dp[MAX_N][MAX_S + 1];
// Valores dos itens "novos".
int NV[MAX_N];
// Pesos dos itens "novos".
int NW[MAX_N];
// Total dos itens "novos".
int m = 0;
class MaxQueue {
private:
deque<pair<int, int>> Q;
int time_added;
int time_removed;
int delta;
public:
MaxQueue() {
delta = time_added = time_removed = 0;
}
void push(int x) {
int x_delta = x - delta;
while (!Q.empty() && Q.back().first < x_delta) {
Q.pop_back();
}
Q.push_back({x_delta, time_added++});
}
void pop() {
if (Q.empty()) {
return;
}
if (time_removed == Q.front().second) {
Q.pop_front();
}
time_removed++;
}
int max() {
return Q.front().first + delta;
}
void add_all(int d) {
delta += d;
}
};
/**
* Baseado na solução apresentada em sala de aula para
* o problema da mochila limitada em 11/06.
*/
int find_best_solution() {
// Primeiro passo: agrupar em potencias de dois + resto.
for (int i = 0; i < N; i++) {
int pos = 0;
while ((1 << pos) < K[i]) {
NW[m] = (1 << pos) * W[i];
NV[m] = (1 << pos) * V[i];
K[i] -= (1 << pos);
pos++;
m++;
}
if (K[i] > 0) {
NW[m] = K[i] * W[i];
NV[m] = K[i] * V[i];
m++;
}
}
// Segundo passo: usar o problema da mochila normal
// com os novos pesos e valores.
for (int c = 0; c <= S; c++) {
dp[m][c] = 0;
}
for (int i = m - 1; i >= 0; i--) {
for (int c = 0; c <= S; c++) {
// Não pegar o elemento.
dp[i][c] = dp[i + 1][c];
if (NW[i] <= c) {
dp[i][c] = max(dp[i][c], NV[i] + dp[i + 1][c - NW[i]]);
}
}
}
return dp[0][S];
}
/**
* Difícil achar referências que usem a fila do jeito que foi passado em aula,
* mas estes links comentam da ideia da janela deslizante.
*
* Referências:
* - https://cp-algorithms.com/dynamic_programming/knapsack.html
* - https://books.google.com.br/books?id=u5DB7gck08YC&lpg=PA211&pg=PA194&redir_esc=y#v=onepage&q&f=false
* - https://dhruvbird.blogspot.com/2011/09/integer-01-bounded-knapsack-problem.html
* - https://blog.mitrichev.ch/2011/07/integral-bounded-knapsack-problem.html
* - https://programming.vip/docs/monotone-queue-optimization-for-multiple-knapsack-problems.html
*/
int find_best_solution_sliding_window() {
for (int i = N - 1; i >= 0; i--) {
// Itera sobre todos as possíveis classes de W[i]. Vai só até W[i] - 1
// pois sempre vai ter um rest e um mult tal que color + mult * W[i] = S.
for (int color = 0; color < W[i]; color++) {
// Cada classe tem sua fila.
MaxQueue queue;
int window_size = 0;
// Itera entre os próximos casos da mesma classe.
for (int mult = 0; color + mult * W[i] <= S; mult++) {
queue.add_all(V[i]);
queue.push(dp[i + 1][color + mult * W[i]]);
// Chegou ao limite de itens, precisa avançar a janela.
if (++window_size > K[i] + 1) {
queue.pop();
window_size--;
}
dp[i][color + mult * W[i]] = queue.max();
}
}
}
return dp[0][S];
}
int main(int argc, char * argv[]) {
cin >> S >> N;
for (int i = 0; i < N; i++) {
cin >> V[i] >> W[i] >> K[i];
}
cout << find_best_solution_sliding_window() << '\n';
return EXIT_SUCCESS;
}
