#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using LL = long long;
int main() {
cin.tie(nullptr)->ios_base::sync_with_stdio(false);
LL s, n;
cin >> s >> n;
vector <LL> weight (n), val (n), copy (n);
for (int i = 0; i < n; i++) cin >> val[i] >> weight[i] >> copy[i];
n = weight.size ();
vector < vector <LL> > dp (n + 1, vector <LL> (s + 1));
for (LL i = 1; i <= n; i++) {
for (LL j = s; j >= 0; j--) {
dp[i][j] = dp[i - 1][j];
for (LL k = 1; k <= copy[i - 1] and k * weight[i - 1] <= s and k * weight[i - 1] <= j; k++) {
dp[i][j] = max (dp[i][j], dp[i - 1][j - k * weight[i - 1]] + k * val[i - 1]);
}
}
}
cout << *max_element (all (dp[n])) << '\n';
return 0;
}
