#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mxS = 2005; // Slightly larger for safety
ll dp[mxS];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int s, n;
cin >> s >> n;
// Use specific variables instead of array for readability and speed
// dp array initialization
fill(dp, dp + s + 1, -1e18); // Initialize only up to S
dp[0] = 0;
ll ans = 0;
for(int i = 0; i < n; i++) {
ll val, w, k;
cin >> val >> w >> k;
// Optimization: If weight is 0 or value is negative/useless, skip
if (k == 0 || w == 0) continue;
// HYBRID OPTIMIZATION START
// If total weight of all copies exceeds capacity, treat as infinite (Complete Knapsack)
if (w * k >= s) {
for (int j = w; j <= s; j++) {
if (dp[j-w] != -1e18) {
dp[j] = max(dp[j], dp[j-w] + val);
}
ans = max(ans, dp[j]);
}
}
// Otherwise, use your existing Binary Splitting method
else {
ll use = k;
for (ll j = 1; use > 0; j *= 2) {
ll take = min(use, j);
ll weight_chunk = take * w;
ll value_chunk = take * val;
for (int pos = s; pos >= weight_chunk; pos--) {
if (dp[pos - weight_chunk] != -1e18) {
dp[pos] = max(dp[pos], dp[pos - weight_chunk] + value_chunk);
}
ans = max(ans, dp[pos]);
}
use -= take;
}
}
// HYBRID OPTIMIZATION END
}
cout << ans;
return 0;
}
