#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ms(x, y) memset(x, y, sizeof x)
#define sp ,' ',
#define el ,'\n'
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using l2 = array<ll, 2>;
template<typename... Args>
inline void out(Args... args) {
(cout << ... << args);
}
struct r {
template<typename T>
inline r& operator,(T& x) {
cin >> x;
return *this;
}
} in;
#define in in,
ll s, n, dp[2001][2001], ans;
vector<l2> items[2001];
void solve() {
in s, n;
for (int i = 0; i < n; i++) {
ll v, w, k; in v, w, k;
k = min(k, (s+w-1) / w);
items[w].push_back({v, k});
}
for (ll i = 1; i <= s; i++) {
sort(items[i].begin(), items[i].end(), greater<l2>());
ll cur = 0;
for (int j = 0; j < items[i].size(); j++) {
cur += i * items[i][j][1];
if (cur >= s) { items[i].resize(j+1); break; }
}
for (int j = 1; j < items[i].size(); j++) items[i][j][1] += items[i][j-1][1];
// out(i el);
// for (int j = 0; j < items[i].size(); j++) out(items[i][j][0] sp items[i][j][1] el);
}
for (int i = 1; i <= s; i++) for (int j = 1; j <= s; j++) {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
ll v = 0, w = 0, at = 0;
for (int k = 0; k <= s/i; k++) {
if (at < items[i].size() && k >= items[i][at][1]) at++;
if (at >= items[i].size()) break;
v += items[i][at][0];
w += i;
if (w > j) break;
dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v);
}
}
for (int j = 0; j <= s; j++) ans = max(ans, dp[s][j]);
out(ans el);
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
// in(t);
while (t--) solve();
}
