#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int s, n;
cin >> s >> n;
vector<ll> v(n+1), w(n+1), k(n+1);
for (int i = 1; i <= n; ++i)
cin >> v[i] >> w[i] >> k[i];
// dp[i][j] = max value using first i items with capacity j
vector<vector<ll>> dp(n+1, vector<ll>(s+1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= s; ++j) {
// option 0: take none of item i
dp[i][j] = dp[i-1][j];
// try taking t copies of item i, 1 <= t <= k[i]
// stop if t*w[i] > j
for (ll t = 1; t <= k[i] && t * w[i] <= j; ++t) {
dp[i][j] = max(
dp[i][j],
dp[i-1][ j - t * w[i] ] // leftover capacity
+ t * v[i] // value of t copies
);
}
}
}
cout << dp[n][s] << "\n";
return 0;
}
