#include <bits/stdc++.h>
using namespace std;
void solve() {
int s, n;
cin >> s >> n;
vector<int> values, weights;
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
for (int j = 0; j < k; j++) {
values.push_back(v);
weights.push_back(w);
}
}
vector<vector<int>> dp(values.size() + 1, vector<int>(s + 1));
for (int i = 1; i <= values.size(); i++) {
for (int j = 1; j <= s; j++) {
if (weights[i - 1] <= j) {
dp[i][j] =
max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[n][s] << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("speed.in", "r", stdin);
// freopen("speed.out", "w", stdout);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
