#include <bits/stdc++.h>
#include <climits>
using namespace std;
using ll = long long;
using ui = unsigned int;
void solve() {
int S, n;
cin >> S >> n;
map<int, vector<pair<int, int>>> by_weight;
for (auto i = 0; i < n; ++i) {
int v, w, k;
cin >> v >> w >> k;
if (k == 0 || w > S) {
continue;
}
by_weight[w].push_back({v, k});
}
vector<vector<ll>> dp(by_weight.size() + 1, vector<ll>(S + 1, LLONG_MIN));
dp[0][0] = 0;
int i = 1;
for (auto &[w, items] : by_weight) {
sort(items.begin(), items.end(), std::greater<pair<int, int>>());
for (int j = 0; j <= S; ++j) {
dp[i][j] = dp[i - 1][j];
size_t cur_item = 0;
int cur_used = 0;
int n_items = 0;
ll value = 0;
while ((n_items + 1) * w <= j && cur_item < items.size()) {
n_items++;
value += items[cur_item].first;
if (dp[i - 1][j - n_items * w] != LLONG_MIN) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - n_items * w] + value);
}
cur_used++;
if (cur_used == items[cur_item].second) {
cur_item++;
cur_used = 0;
}
}
}
++i;
}
ll ans = 0;
for (auto j = 0; j <= S; ++j) {
ans = max(ans, dp[by_weight.size()][j]);
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
