#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = (ll)(1e18) + 13; int main() { ios::sync_with_stdio(0); cin.tie(0); int s, n; cin >> s >> n; int a[n][3]; for (int i=0; i<n; i++) { for (int j=0; j<3; j++) { cin >> a[i][j]; } } vector<ll> dp(s+5, -INF); dp[0] = 0; for (int i=s; i>=0; i--) { int x = 0; ll v = 0; queue<int> q; for (int j=0; j<n; j++) { int k = a[j][2]; while (k--) { // deduct if exceeded while (x + a[j][1] > i) { if (q.empty()) { break; } int l = q.front(); q.pop(); x -= a[l][1]; v -= a[l][0]; } if (x + a[j][1] > i) { break; } x += a[j][1]; v += a[j][0]; q.push(j); if (dp[i-x] > -INF) { // cerr << i << ' ' << x << ' ' << v << '\n'; dp[i] = max(dp[i], dp[i-x] + v); } } } } ll ans = 0; for (int i=0; i<=s; i++) { ans = max(ans, dp[i]); } cout << ans << '\n'; }