#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
struct Item {
ll w, v;
};
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
if (k * w >= S) {
// Aplicamos a lógica do Knapsack ILIMITADO (loop para frente)
for (int j = w; j <= S; j++) {
dp[j] = max(dp[j], dp[j - w] + v);
}
} else {
// Se o item é realmente limitado, usamos o splitting binário
ll c = 1;
while (k > c) {
k -= c;
ll current_w = c * w;
ll current_v = c * v;
// Aplicamos Knapsack 0/1 para cada pacote (loop para trás)
for (int j = S; j >= current_w; j--) {
dp[j] = max(dp[j], dp[j - current_w] + current_v);
}
c *= 2;
}
// Pacote final com o resto
ll current_w = k * w;
ll current_v = k * v;
for (int j = S; j >= current_w; j--) {
dp[j] = max(dp[j], dp[j - current_w] + current_v);
}
}
}
cout << dp[S] << endl;
return 0;
}
