#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int S = 2e3 + 5;
int s, n;
int v[N], w[N], k[N];
priority_queue<pair<int, int>> pq[S];
vector<pair<int, int>> obj;
int f[S];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i] >> k[i];
pq[w[i]].push({v[i], k[i]});
}
for (int i = 1; i <= s; i++) {
int cur = s;
while (!pq[i].empty() && cur - i >= 0) {
int u = pq[i].top().first;
int cnt = pq[i].top().second;
obj.emplace_back(i, u);
pq[i].pop();
cnt--;
if (cnt > 0) {
pq[i].push({u, cnt});
}
cur -= i;
}
}
memset(f, -0x3f, sizeof(f));
f[0] = 0;
for (auto x : obj) {
for (int i = s; i - x.first >= 0; i--) {
f[i] = max(f[i], f[i - x.first] + x.second);
}
}
cout << *max_element(f, f + s + 1) << '\n';
return 0;
}
