#include <bits/stdc++.h>
int64_t s, n;
std::vector<std::array<int64_t,3>> v;
const int64_t maxv = 2001;
std::array<int64_t,maxv> dp;
int main() {
std::cin >> s >> n;
v.resize(n); for (auto& x : v) std::cin >> x[0] >> x[1] >> x[2];
std::fill(dp.begin(), dp.end(), -1);
dp[0] = 0;
for (int64_t item = 0; item < n; item++) {
int64_t V = v[item][0];
int64_t W = v[item][1];
int64_t K = v[item][2];
for (int64_t i = s-W; i >= 0; i--) {
if (dp[i] == -1) continue;
for (int64_t j = 1; i + j*W <= s; j++) { if (j > K) break;
dp[i+j*W] = std::max(dp[i+j*W], dp[i] + j*V);
}
}
}
int64_t sol = 0; for (int64_t i = 0; i < maxv; i++) sol = std::max(sol, dp[i]);
std::cout << sol << "\n";
}
