#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> V[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 x: S[w]) V[w].push_back(x);
reverse(V[w].begin(), V[w].end());
}
for (int w = 1; w <= s; w++) {
for (int i = s; i >= w; i--) {
int k = 0, v = 0;
for (int x: V[w]) { k++; v += x;
if (i - w * k < 0) break;
dp[i] = max(dp[i], dp[i - w * k] + v);
}
}
}
cout << dp[s] << '\n';
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int T = 1; // cin >> T;
while (T--) {
solve();
}
}
