#include <bits/stdc++.h>
//#include "factories.h"
#define f first
#define s second
#define int long long
using namespace std;
const int maxn = 2010;
vector<pair<int, int>> g[maxn];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while(tt--) {
int s, n;
cin >> s >> n;
int v[n], w[n], k[n];
for(int i = 0;i < n;i++) {
cin >> v[i] >> w[i] >> k[i];
g[w[i]].push_back({v[i], k[i]});
}
vector<int> a, b;
a.push_back(0);
b.push_back(0);
//a-tezina, b-value
for(int i = 1;i <= s;i++) {
sort(g[i].begin(), g[i].end());
reverse(g[i].begin(), g[i].end());
int x = s / i, ptr = 0;
while(x > 0 && ptr < (int)g[i].size()) {
if(x >= g[i][ptr].s) {
x -= g[i][ptr].s;
for(int j = 0;j < g[i][ptr].s;j++) {
a.push_back(i);
b.push_back(g[i][ptr].f);
}
}
else {
for(int j = 0;j < x;j++) {
a.push_back(i);
b.push_back(g[i][ptr].f);
}
x = 0;
}
ptr++;
}
}
int m = a.size();
vector<vector<int>> dp(m, vector<int>(s + 1));
for(int i = 1;i < m;i++) {
for(int j = 1;j <= s;j++) {
if(j < a[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + b[i]);
}
}
cout << dp[m - 1][s];
}
return 0;
}
