pragma GCC optimize("Ofast,unroll-loops")

pragma GCC target("avx,avx2,fma")

include <bits/stdc++.h>

using namespace std;

typedef long long ll; const int MAX = 2002; vector<pair<ll, ll>> a[MAX]; ll f[MAX][MAX], s, n, u, v, w, k, total;

void solve() { cin >> s >> n; for (int i = 1; i <= n; i++) { cin >> v >> w >> k; a[w].push_back({v, k}); } for (int i = 1; i <= 2000; i++) sort(a[i].begin(), a[i].end(), greater<pair<ll, ll>>()); for (int i = 1; i <= s; i++) { for (int j = 1; j <= s; j++) { total = 0; ll temp = 0; f[i][j] = f[i — 1][j]; for (auto u : a[i]) { if (total + u.second * i <= j) { total += u.second * i; temp += u.second * u.first; f[i][j] = max(f[i][j], temp + f[i — 1][j — total]); } else { temp += (j — total) / i * u.first; total += (j — total) / i * i; f[i][j] = max(f[i][j], temp + f[i — 1][j — total]); break; } } f[i][j] = max(f[i][j], temp + f[i — 1][j — total]); //if (i > 19) cout << f[i][j] << " "; } //if (i > 19) cout << "\n"; } cout << f[s][s]; }

int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); }