#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
#define maxs(a, b) (a = max(a,b))
int s, n;
vector<pii> sepw[2001];
int dp[2001];
inline void add(int w, int v) {
for(int i=s-w; i>=0; i--)
maxs(dp[i+w], dp[i]+v);
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> s >> n;
for(int i=0, v, w, k; i<n; i++) {
cin >> v >> w >> k;
sepw[w].push_back({-v, k});
}
for(int w=1; w<=s; w++) {
sort(sepw[w].begin(), sepw[w].end());
int cur=0;
for(auto i : sepw[w])
for(int j=0; j<i.Y && cur*w<=s; j++)
add(w, -i.X),
cur++;
}
cout << dp[s] << '\n';
return 0;
}
