#include "bits/stdc++.h"
using namespace std;
struct node {
long long v, w, k;
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
long long s, n;
cin >> s >> n;
vector<node> v(n);
for (int i = 0; i < n; i++)
cin >> v[i].v >> v[i].w >> v[i].k;
sort(begin(v), end(v), [](node a, node b) {
if (a.v == b.v) return a.w < b.w;
return a.v > b.v;
});
long long dp[s + 1];
memset(dp, 0, sizeof dp);
long long ans = 0;
for (int i = 0; i < n; i++) {
for (long long j = s; j >= 0; j--) {
for (long long a = min(v[i].k, (s - j) / v[i].w); a >= max(min(v[i].k, (s - j) / v[i].w) - 0, 0ll); a--) {
dp[j + v[i].w * a] = max(dp[j + v[i].w * a], dp[j] + v[i].v * a);
ans = max(ans, dp[j + v[i].w * a]);
}
for (long long a = 0; a <= min(0ll, min(v[i].k, (s - j) / v[i].w)); a++) {
dp[j + v[i].w * a] = max(dp[j + v[i].w * a], dp[j] + v[i].v * a);
ans = max(ans, dp[j + v[i].w * a]);
}
}
}
cout << ans << '\n';
}
