#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
ll s, n;
cin >> s >> n;
vector<vector<pair<ll, ll>>> w(s + 5);
for (int i = 0; i < n; ++i) {
ll v, we, k;
cin >> v >> we >> k;
w[we].push_back({v, k});
}
vector<pair<ll, ll>> v;
for (int i = 0; i < s + 2; ++i) {
if (w[i].empty()) continue;
sort(w[i].begin(), w[i].end());
ll ct = (s + i - 1) / i;
for (; !w[i].empty() && ct > 0; --ct) {
w[i].back().second--;
v.push_back({i, w[i].back().first});
if (w[i].back().second == 0) w[i].pop_back();
}
}
vector<ll> dp(s + 10, 0);
dp[0] = 0;
for (auto &item : v) {
for (int j = s + 5; j >= item.first; --j) {
dp[j] = max(dp[j], dp[j - item.first] + item.second);
}
}
ll res = 0;
for (int i = 0; i <= s; ++i) {
res = max(res, dp[i]);
}
cout << res << endl;
}
int main() {
solve();
return 0;
}
