#include <bits/stdc++.h>
using namespace std;
int main() {
int S, N;
cin >> S >> N;
vector<int> V(N), W(N), K(N);
for (int i = 0; i < N; i++) cin >> V[i] >> W[i] >> K[i];
// Binary splitting to convert bounded -> 0/1 items
vector<int> newV, newW;
for (int i = 0; i < N; i++) {
int copies = K[i], power = 1;
while (copies > 0) {
int take = min(power, copies);
newV.push_back(take * V[i]);
newW.push_back(take * W[i]);
copies -= take;
power *= 2;
}
}
vector<int> dp(S + 1, 0); // only 1D DP array
for (int i = 0; i < (int)newV.size(); i++) {
for (int s = S; s >= newW[i]; s--) {
dp[s] = max(dp[s], dp[s - newW[i]] + newV[i]);
}
}
cout << dp[S] << endl;
return 0;
}
