#include <algorithm>
#include <iostream>
typedef long long int ll;
int main() {
ll s, n; // 15 3
std::cin >> s >> n;
auto v = new ll[n + 1]; // 10 7 6
auto w = new ll[n + 1]; // 10 7 6
auto k = new ll[n + 1]; // 10 7 6
for (ll i = 1; i <= n; i++) {
std::cin >> v[i] >> w[i] >> k[i];
}
v[0] = 0;
w[0] = 0;
k[0] = 0;
ll dp[s + 1];
for (ll i = 0; i <= s; i++) {
dp[i] = 0;
}
for (ll i = 1; i <= n; i++) {
for (ll j = s; j >= w[i]; j--) {
for (ll m = 1; m <= k[i] && j - m * w[i] >= 0; m++) {
dp[j] = std::max(dp[j], dp[j - m * w[i]] + m * v[i]);
}
}
}
std::cout << dp[s] << '\n';
}
