// author: khba
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int inf = (int)1e18;
#ifdef khba
#include "C:\Users\Asus\Desktop\khba\debug.h"
#else
#define print(...) 42
#endif
int32_t main() {
#ifdef khba
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int S, n; cin >> S >> n;
vector <array<int, 3>> a(n);
for (auto &[v, w, k] : a) cin >> v >> w >> k;
sort(rbegin(a), rend(a));
vector <int> val[S + 1];
for (auto &[v, w, k] : a)
while (val[w].size() < S / w and k--) val[w].push_back(v);
vector <int> dp(S + 1, -inf);
dp[0] = 0;
for (int w = 1; w <= S; ++w) {
for (int i = 0; i < val[w].size(); ++i) {
for (int W = S - w; W >= 0; --W)
dp[W + w] = max(dp[W + w], dp[W] + val[w][i]);
}
}
cout << *max_element(begin(dp), end(dp));
return 0;
}
