#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int s, n;
cin >> s >> n;
map<int, vector<pair<int, int>>> mp;
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
mp[w].emplace_back(v, k);
}
int m = int(mp.size());
vector<vector<int64_t>> best(m + 1, vector<int64_t>(s + 1));
int p = 0;
for (auto [w, a] : mp) {
sort(a.rbegin(), a.rend());
for (int W = 0; W <= s; W++) {
best[p + 1][W] = max(best[p + 1][W], best[p][W]);
int k = 1, i = 0;
int used = 0;
int64_t cost = 0;
while (k * w <= W && i < int(a.size())) {
cost += a[i].first;
used++;
best[p + 1][W] = max(best[p + 1][W], best[p][W - k * w] + cost);
if (used == a[i].second) {
used = 0;
i++;
}
k++;
}
}
p++;
}
cout << *max_element(best[m].begin(), best[m].end()) << '\n';
return 0;
}
