#include <bits/stdc++.h> using namespace std; #define ll long long #define ar array void solve() { int m, n; cin >> m >> n; vector<vector<ll>> dp(m + 1, vector<ll> (m + 1, 0)); vector<ar<int, 2>> W[m + 1]; for (int i = 0; i < n;i++) { int x, y, z; cin >> x >> y >> z; if (y <= m) W[y].push_back({x, z}); } for (int i = 1; i <= m;i++) { sort(W[i].rbegin(), W[i].rend()); for (int j = 1; j <= m;j++) { dp[i][j] = dp[i - 1][j]; ll val = 0; int id = 0; int taken = 0; for (int k = 1; k * i <= j;k++) { if (id < W[i].size() && W[i][id][1] == taken) { id++; k--; taken = 0; continue; } if (id < W[i].size()) { taken++; val += W[i][id][0]; } dp[i][j] = max(dp[i][j], dp[i - 1][j - k * i] + val); } } } cout << *max_element(dp.back().begin(), dp.back().end()); } signed main() { cin.tie(nullptr)->sync_with_stdio(false); solve(); return 0; }