#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, val;
for (LL i = 0; i < n; i++) {
LL v, w, k;
cin >> v >> w >> k;
for (LL j = 1; j * w <= s and j <= k; j++) {
weight.push_back (j * w);
val.push_back (v);
}
}
n = weight.size ();
vector < vector <LL> > dp (n + 1, vector <LL> (s + 1));
vector < vector <bool> > isAvail (n + 1, vector <bool> (s + 1));
isAvail[0][0] = 1;
for (LL i = 1; i <= n; i++) {
for (LL j = s; j >= 0; j--) {
dp[i][j] = dp[i - 1][j];
isAvail[i][j] = isAvail[i - 1][j];
if (j - weight[i - 1] >= 0 and isAvail[i - 1][j - weight[i - 1]]) {
isAvail[i][j] = 1;
dp[i][j] = max (dp[i][j], dp[i - 1][j - weight[i - 1]] + val[i - 1]);
}
}
}
cout << *max_element (all (dp[n])) << '\n';
return 0;
}
