#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define test(v) \ for (auto &x : (v)) { \ cout << x << " "; \ } \ cout << "\n"; #define test2d(v) \ for (int i = 0; i < (int)v.size(); i++) { \ for (int j = 0; j < (int)v[i].size(); j++) { \ cout << v[i][j] << " "; \ } \ cout << '\n'; \ } #define pb push_back vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; mt19937 rng((int)chrono::steady_clock::now().time_since_epoch().count()); int hashp = uniform_int_distribution<int>(10, 1e9)(rng); int hashm1 = 1e9+7; int hashm2 = 1e9+9; int MOD = 1e9; int MV = 1e18; void solve(){ int s, n; cin >> s >> n; vector<vector<array<int, 2>>> a(s+1); vector<int> dp(s+1, 0); for(int i = 0; i < n; i++){ int v, w, k; cin >> v >> w >> k; a[w].pb({v, k}); } for(int i = 1; i <= s; i++){ if(a[i].empty()) continue; sort(a[i].begin(), a[i].end(), greater<>()); vector<int> costs; int limit = s / i; for (auto &p : a[i]) { if (costs.size() >= limit) break; int val = p[0]; int count = p[1]; while (count > 0 && costs.size() < limit) { costs.pb(val); count--; } } for (size_t x = 1; x < costs.size(); x++) { costs[x] += costs[x-1]; } for(int j = s; j >= i; j--){ for(int k = 1; k <= costs.size(); k++){ int prev_w = j - k * i; if (prev_w < 0) break; dp[j] = max(dp[j], dp[prev_w] + costs[k-1]); } } } cout << dp[s]; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); /* freopen("snakes.in", "r", stdin); freopen("snakes.out", "w", stdout); */ solve(); return 0; }