#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }
using ll = long long;
using pii = std::pair<int, int>;
const int SMAX = 5e3;
const int NMAX = 1e5;
using namespace std;
vector<pair<int, int>> obj;
vector<pair<int, int>> vec[SMAX + 5];
int dp[SMAX + 5], n, S;
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> S >> n;
for (int i = 1, v, w, k; i <= n; ++i) {
cin >> v >> w >> k;
vec[w].push_back({v, k});
}
fill(dp + 1, dp + S + 1, INT_MIN);
dp[0] = 0;
for (int w = 1; w <= S; ++w) {
sort(all(vec[w]), std::greater());
int sum_w = 0;
for (auto &[v, k] : vec[w]) {
for (int i = 0; i < k; ++i) {
sum_w += w;
if (sum_w > S) break;
for (int j = S; j >= w; --j)
dp[j] = max(dp[j], dp[j - w] + v);
}
}
}
cout << *max_element(dp, dp + S + 1) << '\n';
return 0;
}
