#include <bits/stdc++.h>
using namespace std;
const int MAX_S = 10005;
long long v[MAX_S], w[MAX_S];
long long dp[MAX_S];
int k[MAX_S];
void process_item(int idx, int s) {
long long value = v[idx];
long long weight = w[idx];
int count = k[idx];
// Process in powers of two
for (int i = 1; i <= count; i *= 2) {
long long num = min(i, count); // Take the minimum of current power of two and remaining count
count -= num;
// Update dp array in reverse order
for (int j = s; j >= num * weight; j--) {
dp[j] = max(dp[j], dp[j - num * weight] + num * value);
}
}
// Process the remaining items
if (count > 0) {
for (int j = s; j >= count * weight; j--) {
dp[j] = max(dp[j], dp[j - count * weight] + count * value);
}
}
}
int main() {
int s, n;
cin >> s >> n;
// Read inputs
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i] >> k[i]; // v[i] = value, w[i] = weight, k[i] = max times we can take item i
}
// Initialize dp array
fill(dp, dp + s + 1, 0);
// Process each item
for (int i = 1; i <= n; i++) {
process_item(i, s);
}
cout << dp[s] << endl;
return 0;
}
