#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[n + 1][s + 1];
for (ll i = 0; i <= n; i++) {
for (ll j = 0; j <= s; j++) {
dp[i][j] = 0;
}
}
for (ll i = 1; i <= n; i++) {
for (ll j = 0; j <= s; j++) {
dp[i][j] = dp[i - 1][j];
for (ll m = 1; m <= k[i] && j - m * w[i] >= 0; m++) {
dp[i][j] = std::max(dp[i][j], dp[i - 1][j - m * w[i]] + m * v[i]);
}
}
}
std::cout << dp[n][s] << '\n';
}
