// https://oj.uz/problem/view/NOI18_knapsack > p83
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int S, n; cin >> S >> n;
vector<int> v(n);
vector<int> w(n);
vector<int> K(n);
for (int i=0; i<n; i++) cin >> v[i] >> w[i] >> K[i];
int mx = 0;
for (int i=0; i<n; i++) {
K[i] = min(K[i], (S/w[i])+min(S%w[i], 1));
mx = max(mx, K[i]);
}
K.push_back(0);
vector<vector<vector<int>>> dp(2, vector<vector<int>> (S+1, vector<int> (mx+1, 0)));
for (int i=n-1; i>=0; i--) {
for (int P=0; P<=S; P++) {
for (int k=0; k<=mx; k++) {
dp[i&1][P][k] = dp[(i+1)&1][P][K[i+1]];
if (k>0 and P>=w[i]) {
dp[i&1][P][k] = max(
dp[i&1][P][k],
dp[i&1][P-w[i]][k-1] + v[i]
);
}
}
}
}
cout << dp[0&1][S][K[0]] << endl;
return 0;
}
