#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2000 + 24;
int n, s; multiset<int> S[N];
int dp[N]; vector<int> W[N];
void solve() {
cin >> s >> n;
for (int i = 1; i <= n; i++) {
int v, w, k; cin >> v >> w >> k;
k = min(k, s / w);
while (k--) {
S[w].insert(v);
if ((int) S[w].size() > s / w) {
S[w].erase(S[w].begin());
}
}
}
for (int w = 1; w <= s; w++) {
for (int v: S[w]) {
W[w].push_back(v);
}
reverse(W[w].begin(), W[w].end());
}
for (int w = 1; w <= s; w++) {
for (int v: W[w]) {
for (int i = s; i >= w; i--) {
dp[i] = max(dp[i], dp[i - w] + v);
}
}
}
cout << dp[s] << '\n';
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int T = 1; // cin >> T;
while (T--) {
solve();
}
}
