#include <bits/stdc++.h>
typedef long long ll;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
ll s, n;
std::cin >> s >> n;
std::vector<std::vector<std::pair<ll, ll>>> items(2001);
for (ll i = 0, v, w, k; i < n; ++i) {
std::cin >> v >> w >> k;
items[w].push_back({v, k});
}
// for the same weight, prefer more valauble items
for (auto &i : items) {
std::sort(i.rbegin(), i.rend());
}
// actual items: O(s log s) many
std::vector<std::pair<ll, ll>> a;
for (ll w = 1; w <= 2000; ++w) {
ll max = 2000 / w;
for (auto [v, k] : items[w]) {
while (k--) {
max--;
a.push_back({w, v});
if (max == 0) {
break;
}
}
if (max == 0) {
break;
}
}
}
std::vector<std::vector<ll>> dp(a.size() + 1, std::vector<ll>(s + 1));
for (ll i = a.size(); i >= 0; --i) {
for (ll j = s; j >= 0; --j) {
if (i == a.size()) {
dp[i][j] = 0;
continue;
}
dp[i][j] = dp[i + 1][j];
if (j + a[i].first <= s) {
dp[i][j] = std::max(dp[i][j], dp[i + 1][j + a[i].first] + a[i].second);
}
}
}
std::cout << dp[0][0] << '\n';
}
