#include <bits/stdc++.h>
using namespace std;
#define inf 1e15
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef SUBLIME
freopen("inputf.in", "r", stdin);
freopen("outputf.out", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
int n, w;
cin >> w >> n;
vector<pair<long long, long long>> obj;
for (int i = 0; i < n; i++) {
long long wt, val, copy;
cin >> val >> wt >> copy;
for (long long p = 1; copy; p <<= 1) {
long long take = min(p, copy);
obj.push_back({take * wt, take * val});
copy -= take;
}
}
n = obj.size();
vector<vector<long long>> dp(n + 1, vector<long long>(w + 1, 0));
for (int no = 1; no <= n; no++) {
auto [wt, val] = obj[no - 1];
for (int rw = 0; rw <= w; rw++) {
dp[no][rw] = dp[no - 1][rw];
if (rw >= wt)
dp[no][rw] = max(dp[no][rw], dp[no - 1][rw - wt] + val);
}
}
cout << *max_element(dp[n].begin(), dp[n].end()) << "\n";
return 0;
}
