#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
using namespace std;
const int MAX_N = 100000;
const int MAX_S = 2000;
int S;
int N;
// int * V; // int V[MAX_N];
// int * W; // int W[MAX_N];
// int * K; // int K[MAX_N];
vector<int> V;
vector<int> W;
vector<int> K;
int dp[2][MAX_S + 1]; // int dp[MAX_N][MAX_S + 1];
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;
}
};
/**
* 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() {
int ant = 0, act = 1;
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 k = 0;
// Itera entre os próximos casos da mesma classe.
// for (int mult = 0; color + mult * W[i] <= S; mult++) {
// int c = color + mult * W[i];
// Multiplicações costumam ser mais custosas, então este faz apenas somas.
for (int c = color; c <= S; c += W[i]) {
queue.add_all(V[i]);
queue.push(dp[ant][c]);
// Chegou ao limite de itens, precisa avançar a janela.
if (k > K[i]) {
queue.pop();
} else {
k++;
}
dp[act][c] = queue.max();
}
}
swap(act, ant);
}
return dp[ant][S];
}
int main(int argc, char * argv[]) {
cin >> S >> N;
V.resize(N);
W.resize(N);
K.resize(N);
for (int i = 0; i < N; i++) {
cin >> V[i] >> W[i] >> K[i];
}
cout << find_best_solution() << '\n';
return EXIT_SUCCESS;
}
