#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pp;
#define all(a) (a).begin(), (a).end()
#define print(a) for (const auto &x : (a)) cout << x << ' '; cout << '\n';
const int N = 2e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e15;
/*
1- Read input
2- val, k
3- numIdx = s / i.
4- If i
*/
void solve() {
int s, n;
cin >> s >> n;
vector<vector<pp> > cur(s + 1);
for(int i = 0, val, w, k; i < n; ++i) {
cin >> val >> w >> k;
cur[w].push_back({val, k});
}
for(int i = 1; i <= s; ++i) {
sort(cur[i].rbegin(), cur[i].rend());
}
vector<vector<int> > a(s + 1);
for(int i = 1; i <= s; ++i) {
a[i].assign((s / i) + 2, 0);
int idx = 1;
for(auto [val, k] : cur[i]) {
while(idx < a[i].size() and k) {
a[i][idx] = val + a[i][idx - 1];
idx++;
k--;
}
}
}
/*
Taking one or two or 3
W and val
*/
// cout << a[1][1] << '\n';
vector<vector<pp> > ans(s + 1, vector<pp> (2, {-INF, 0}));
ans[0][0] = ans[0][1] = {0, 0};
for(int i = 1; i <= s; ++i) {
for(int idx = 1; idx < a[i].size(); ++idx) {
// if(a[i][idx] == a[i][idx-1]) break;
int val = a[i][idx];
int w = (idx) * i;
// cout << val << ' ';
for(int j = s; j >= w; --j) {
if(ans[j-w][0].second != i)
ans[j].push_back({val + ans[j - w][0].first, i});
if(ans[j-w][1].second != i)
ans[j].push_back({val + ans[j - w][1].first, i});
sort(ans[j].rbegin(), ans[j].rend());
vector<pp> t;
for(auto [x, y] : ans[j]) {
if(t.empty() or t.back().second != y)
t.push_back({x, y});
}
ans[j] = t;
while(ans[j].size() > 2) {
ans[j].pop_back();
}
}
}
// int val = 0;
// for(auto &v : ans) {
// for(auto [x, y] : v) {
// val = max(val, x);
// }
// }
// cout << val << endl;
}
int val = 0;
for(auto &v : ans) {
for(auto [x, y] : v) {
val = max(val, x);
}
}
cout << val << endl;
// cout << *max_element(all(ans)) << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
// cin >> tt;
while (tt--) {
solve();
}
return 0;
}
