#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define ld long double
#define vi vector<int>
#define vii vector<vector<int>>
#define all(v) (v).begin(), (v).end()
#define rep(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define per(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
using namespace std;
const int MOD = 1e9 + 7;
int add(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
return a;
}
int mul(int a, int b) {
(a *= b) %= MOD;
return a;
}
int ceil(int x, int y) {
return (x + y - 1) / y;
}
int bin_pow(int x, int y) {
int res = 1;
while (y) {
if (y & 1) res = res * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return res;
}
template<class T> bool minimize(T& a, T b) {
if (a > b) return a = b, true;
return false;
}
template<class T> bool maximize(T& a, T b) {
if (a < b) return a = b, true;
return false;
}
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 1e17;
const int maxn = 2e6 + 5;
const int B = 2000;
int s, n;
int f[maxn + 5];
vector<pair<int, int>> g[maxn + 5];
void solve(int tc) {
cin >> s >> n;
for (int i = 1; i <= n; ++i) {
int v, w, k; cin >> v >> w >> k;
g[w].push_back({v, k});
}
for (int i = 1; i <= s; ++i) {
sort(g[i].begin(), g[i].end());
int weight = 0;
for (int j = (int)g[i].size() - 1; j >= 0; --j) {
int v = g[i][j].first, am = g[i][j].second;
while (weight + i <= s && am > 0) {
am--;
weight += i;
for (int w = s; w >= i; --w) {
f[w] = max(f[w], f[w - i] + v);
}
}
if (weight + i > s) break;
}
}
cout << f[s];
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc = 1;
//cin >> tc;
for (int i = 1; i <= tc; ++i) {
solve(i);
}
}
