#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const long long NEG = (long long)-9e18;
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int s, n;
if (!(cin >> s >> n)) return 0;
map<int, vector<pii>> W;
for (int i = 0; i < n; ++i) {
int v, w, k; cin >> v >> w >> k;
W[w].push_back({v, k});
}
int groups = (int)W.size();
vector<vector<long long>> dp(groups + 1, vector<long long>(s + 1, NEG));
dp[0][0] = 0;
int cur = 1;
for (auto [weight, items] : W) {
sort(items.begin(), items.end(), greater<pii>());
dp[cur][0] = dp[cur - 1][0];
for (int i = 1; i <= s; ++i) {
dp[cur][i] = dp[cur - 1][i];
int cnt = 0;
int sum = weight, pos = 0, cum = 0;
while (sum <= s && pos < (int)items.size()) {
if (cnt == items[pos].second) {
pos++;
cnt = 0;
continue;
}
cum += items[pos].first;
if (i >= sum && dp[cur - 1][i - sum] != NEG) {
dp[cur][i] = max(dp[cur][i], dp[cur - 1][i - sum] + cum);
}
sum += weight;
cnt++;
}
}
cur++;
}
long long res = 0;
for (int i = 1; i <= s; ++i) res = max(res, dp[cur - 1][i]);
cout << res << '\n';
return 0;
}
