#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void solve() {
int s, n;
cin >> s >> n;
vector<int> dp(s + 1, 0);
for (int i = 0; i < n; ++i) {
int v, w, q;
cin >> v >> w >> q;
// Binary optimization with early break
if (w == 0) {
// Free items - take all
for (int j = s; j >= 0; --j) {
dp[j] += v * q;
}
continue;
}
int max_use = min(q, s / w); // Don't process more than we can possibly use
for (int k = 1; max_use > 0; k <<= 1) {
int take = min(k, max_use);
int chunkV = take * v;
int chunkW = take * w;
for (int j = s; j >= chunkW; --j) {
if (dp[j - chunkW] + chunkV > dp[j]) {
dp[j] = dp[j - chunkW] + chunkV;
}
}
max_use -= take;
}
}
cout << dp[s] << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
