#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
#define int ll
#define uint ull
using ii = pair<int, int>;
using iii = pair<int, ii>;
#pragma GCC optimize("O3")
constexpr int MAXN = 2005;
constexpr int INF = 1e18 + 5;
vector<ii> itemW[MAXN];
int dp[2][MAXN];
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int S, N; cin >> S >> N;
for (int i = 0; i < N; ++i) {
int v, w, k; cin >> v >> w >> k;
itemW[w].emplace_back(v, k);
}
vector<ii> items;
for (int i = 1; i < MAXN; ++i) {
sort(itemW[i].begin(), itemW[i].end(), greater<ii>{});
int p = 0;
for (auto [v, k] : itemW[i]) {
for (int j = 0; j < k; ++j) {
if (p * i > S) break;
items.emplace_back(v, i);
p++;
}
}
}
fill(dp[0], dp[0] + MAXN, -INF);
fill(dp[1], dp[1] + MAXN, -INF);
dp[0][0] = 0;
dp[1][0] = 0;
int ans = 0;
for (int i = 0; i < items.size(); ++i) {
int j = i&1;
auto [v, w] = items[i];
for (int k = 0; k <= S; ++k) {
dp[j][k] = dp[!j][k];
if (k >= w) dp[j][k] = max(dp[j][k], dp[!j][k-w] + v);
ans = max(ans, dp[j][k]);
}
}
cout << ans;
}
