#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, int> pli;
// const
const ll LINF = (ll)(1e18) + 5;
const int INF = (int)(1e9) + 5;
// loop
#define FOR(i, l, r) for (int i=l; i<r; i++)
#define F0R(i, n) for (int i=0; i<n; i++)
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int S, N;
cin >> S >> N;
vector<vector<pli>> W(S+1);
for (int i=0; i<N; i++) {
int v, w, k;
cin >> v >> w >> k;
W[w].push_back({v, k});
}
for (int i=1; i<=S; i++) {
if (W[i].size() > 0) {
sort(W[i].rbegin(), W[i].rend());
}
}
vector<ll> dp(S+1, -LINF);
dp[0] = 0;
for (int w = 1; w <= S; w++) {
if (W[w].size() == 0) continue;
int maxt = S / w;
int cnt = 0;
for (auto &[v, k] : W[w]) {
for (int i = 0; i < k && cnt < maxt; i++) {
for (int x=S-w; x>=0; x--) {
if (dp[x] > -LINF) {
dp[x + w] = max(dp[x + w], dp[x] + v);
cnt++;
}
}
}
if (cnt >= maxt) {
break;
}
}
}
ll ans = 0;
for (int i=0; i<=S; i++) {
ans = max(ans, dp[i]);
}
cout << ans << '\n';
}
