#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> compute_cop (int x) {
vector<int> store;
int power = 1;
while (x > 0) {
int take = min(power, x);
store.push_back(take);
x -= take;
power *= 2;
}
return store;
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int s, n;
cin >> s >> n;
vector<int> val(n + 1), w(n + 1), k(n + 1);
for (int i = 1; i <= n; i++) cin >> val[i] >> w[i] >> k[i];
vector<int> dp(s + 1, 0);
for (int i = 1; i <= n; i++) {
vector<int> copies = compute_cop(k[i]);
for (int cop : copies) {
for (int j = s; j >= w[i] * cop; j--) {
dp[j] = max(dp[j], dp[j - w[i] * cop] + val[i] * cop);
}
}
}
cout << dp[s] << "\n";
return 0;
}
