#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int S, N; // S: max weight capacity, N: number of item types
cin >> S >> N;
vector<int> V(N), W(N), K(N); // V: values, W: weights, K: quantities
for (int i = 0; i < N; ++i) {
cin >> V[i] >> W[i] >> K[i];
}
// dp array where dp[j] represents max value achievable with weight j
vector<int> dp(S + 1, 0);
// Process each item type
for (int i = 0; i < N; ++i) {
// Create a copy of dp to prevent overwriting values in the same iteration
vector<int> new_dp = dp;
// Go through each possible weight from max to min to avoid using an item multiple times in a single loop
for (int j = 0; j <= S; ++j) {
for (int m = 1; m <= K[i]; ++m) {
int weight = m * W[i];
int value = m * V[i];
if (j >= weight) {
new_dp[j] = max(new_dp[j], dp[j - weight] + value);
} else {
break; // Exit if weight exceeds j
}
}
}
dp = new_dp; // Update dp with new calculated values
}
// The answer is the maximum value achievable within weight S
cout << dp[S] << endl;
return 0;
}
