#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pii pair <int, int>
const int N = 1e5 + 10;
const int S = 2000 + 10;
const ll INF = 1e18;
ll n, k[N], s, q[N];
ll v[N], w[N], dp[S], cnt[S];
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> s >> n;
for (int i = 0; i < n; i++) {
cin >> v[i] >> w[i] >> k[i];
}
iota(q, q + n, 0);
sort(q, q + n, [] (int i, int j) {
if (v[i] != v[j]) return v[i] > v[j];
return i < j;
});
fill(dp, dp + S, -INF);
dp[0] = 0;
for (int ii = 0; ii < n; ii++) {
int i = q[ii];
for (int t = 0; t < k[i]; t++) {
if (cnt[w[i]] * w[i] > s) continue;
for (int j = s; j >= w[i]; j--) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
cnt[w[i]]++;
}
}
cout << *max_element(dp, dp + S) << '\n';
return 0;
}
