#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];
// Convert the problem to multiple 0/1 knapsack problems
int power = 1;
while (count > 0) {
int num = min(power, count);
count -= num;
// Process `num` items of this type
for (int j = s; j >= num * weight; j--) {
dp[j] = max(dp[j], dp[j - num * weight] + num * value);
}
power *= 2; // Move to the next power of 2
}
}
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;
}
