#include <bits/stdc++.h>
using namespace std;
int main() {
int S, N;
cin >> S >> N;
vector<int> value(N), weight(N), copies(N);
for (int i = 0; i < N; ++i) {
cin >> value[i] >> weight[i] >> copies[i];
}
// dp[i][w] = max value using first i items and weight limit w
vector<vector<int>> dp(N + 1, vector<int>(S + 1, 0));
for (int i = 1; i <= N; ++i) {
int v = value[i - 1];
int w = weight[i - 1];
int k = copies[i - 1];
for (int s = 0; s <= S; ++s) {
// First, inherit from not taking the item at all
dp[i][s] = dp[i - 1][s];
// Now try all valid counts from 1 to k of current item
for (int cnt = 1; cnt <= k; ++cnt) {
int total_w = cnt * w;
int total_v = cnt * v;
if (s >= total_w) {
dp[i][s] = max(dp[i][s], dp[i - 1][s - total_w] + total_v);
} else {
break; // no point trying more copies
}
}
}
}
cout << dp[N][S] << endl;
}
