#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
vector<int> weights, values;
for (int i = 0; i < N; i++) {
int value, weight, count;
cin >> value >> weight >> count;
// Binary representation for item multiplicity
for (int power = 1; power <= count; power *= 2) {
weights.push_back(weight * power);
values.push_back(value * power);
count -= power;
}
if (count > 0) {
weights.push_back(weight * count);
values.push_back(value * count);
}
}
vector<int> dp(S + 1, 0);
for (int i = 0; i < weights.size(); i++) {
for (int j = S; j >= weights[i]; j--) {
dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
}
}
cout << dp[S] << endl;
return 0;
}
