#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void solve() {
int s, n;
cin >> s >> n;
map<int, vector<pii>> groups;
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
groups[w].push_back({v, k});
}
int g = groups.size();
vector<vector<ll>> dp(g + 1, vector<ll>(s + 1));
int idx = 1;
for (auto &[w, val] : groups) {
sort(val.begin(), val.end(), greater<pii>());
for (int i = 1; i <= s; i++) {
dp[idx][i] = dp[idx - 1][i];
int cnt = 1, sz = 0, curr = 0;
ll total = 0;
while (i >= cnt * w && sz < val.size()) {
total += val[sz].first;
dp[idx][i] = max(dp[idx][i], dp[idx - 1][i - cnt * w] + total);
cnt++, curr++;
if (curr == val[sz].second) curr = 0, sz++;
}
}
idx++;
}
cout << *max_element(dp[g].begin(), dp[g].end()) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
