#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 1e5;
const int MAXS = 2e3;
ll dp[MAXN + 1][MAXS + 1];
void solve() {
map<int, vector<pii>> by_weights;
int S, N;
cin >> S >> N;
vector<int> V(N), W(N), K(N);
for (int i = 0; i < N; ++i) {
cin >> V[i] >> W[i] >> K[i];
by_weights[W[i]].push_back(make_pair(V[i], K[i]));
}
int id = 1;
for (auto &[k, v] : by_weights) {
sort(v.begin(), v.end(),
[](pii &a, pii &b) { return a.first > b.first; });
for (int i = 0; i <= S; ++i) {
dp[id][i] = dp[id - 1][i];
int cnt = 1, sz = 0, curr = 0;
ll tot = 0;
while (i >= cnt * k && sz < v.size()) {
tot += v[sz].first;
dp[id][i] = max(dp[id][i], dp[id - 1][i - cnt * k] + tot);
++cnt;
++curr;
if (curr == v[sz].second) {
curr = 0;
++sz;
}
}
}
++id;
}
cout << *max_element(dp[by_weights.size()], dp[by_weights.size()] + S + 1)
<< '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
