#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cmath>
#include <cassert>
#include <utility>
using namespace std;
void solve() {
long long s, n;
cin >> s >> n;
vector<vector<pair<long long, long long>>> w(s + 5);
for (int i = 0; i < n; ++i) {
long long v, we, k;
cin >> v >> we >> k;
w[we].push_back({v, k});
}
vector<pair<long long, long long>> v;
for (int i = 0; i < s + 2; ++i) {
if (w[i].empty()) continue;
sort(w[i].begin(), w[i].end());
long long 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<long long> 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);
}
}
long long res = 0;
for (int i = 0; i <= s; ++i) {
res = max(res, dp[i]);
}
cout << res << endl;
}
int main() {
solve();
return 0;
}
