#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int inf = 1e9 + 10;
const int maxw = 3100;
int dp[maxw][maxw];
void init() {
for (int i = 0; i < maxw; i++)
for (int j = 0; j < maxw; j++)
dp[i][j] = -inf;
dp[0][0] = 0;
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(0);
init();
int s, n; cin >> s >> n;
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 cur = 1;
for (auto [weight, items] : W) {
sort(items.begin(), items.end(), greater<pii>());
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 < items.size()) {
if (cnt == items[pos].second) {
pos++;
cnt = 0;
continue;
}
cum += items[pos].first;
if(i >= sum) dp[cur][i] = max(dp[cur][i], dp[cur - 1][i - sum] + cum);
sum += weight; cnt++;
}
}
cur++;
}
int res = 0;
for (int i = 1; i <= s; i++)
res = max(res, dp[cur - 1][i]);
cout << res << '\n';
return 0;
}
