#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
long long v[N], w[N];
long long dp[N];
int k[N];
void binary_decompose(int idx, int n, int s) {
long long value = v[idx];
long long weight = w[idx];
long long count = k[idx];
// Decompose count into powers of two
for (long long i = 1; i <= count; i *= 2) {
long long num = min(i, count); // Take min to avoid exceeding k[i]
count -= num;
// Process this number of items
for (int j = s; j >= num * weight; j--) {
dp[j] = max(dp[j], dp[j - num * weight] + num * value);
}
}
// If count is still left, 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;
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 using binary decomposition
for (int i = 1; i <= n; i++) {
binary_decompose(i, n, s);
}
cout << dp[s] << endl;
return 0;
}
