#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2002;
const long long INF = 1e18 + 18;
void solve()
{
int s, n;
cin >> s >> n;
map<int, vector<pair<int, int>>> byWeight;
for (int i = 0; i < n; i++) {
int w, v, k;
cin >> v >> w >> k;
byWeight[w].emplace_back(v, k);
}
vector<vector<long long>> dp(byWeight.size() + 1, vector<long long> (s + 1));
int index = 1;
for (auto &[w, items] : byWeight) {
sort(items.begin(), items.end(), [](const auto &x, const auto &y) {
return x.first > y.first;
});
for (int j = 0; j <= s; j++) {
dp[index][j] = dp[index - 1][j];
long long cur = 0, sum = 0;
int r = 0, c = 1;
while(r < items.size() && c <= items[r].second) {
cur += items[r].first;
sum += w;
if (sum > j) break;
dp[index][j] = max(dp[index][j], dp[index - 1][j - sum] + cur);
if (++c > items[r].second) {
++r;
c = 1;
}
}
}
index++;
}
cout << dp[byWeight.size()][s] << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
