#include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using vi = vector<int>; #define all(x) (x).begin(), (x).end() ll dp[2001]; int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); int s, n; cin >> s >> n; vector<ll> w[2001]; ll cur_v, cur_w, cur_k; for (int i = 0; i < n; ++i) { cin >> cur_v >> cur_w >> cur_k; while(cur_k) { cur_k--; w[cur_w].push_back(cur_v); } // ll c = 1; // while (c < cur_k) { // if (cur_w * c > s) { // break; // } // w[c * cur_w].push_back(c * cur_v); // cur_k -= c; // c *= 2; // } // if (cur_k > 0) { // if (cur_k * cur_w > s) continue; // w[cur_k * cur_w].push_back(cur_k * cur_v); // } } for (int i = 1; i <= s; ++i) { // cur_wright sort(all(w[i]), greater<ll>()); for (int j = 0 ;j < w[i].size() && i * j <= s; ++j) { // cur_cnt for (int k = s; k >= i; --k) { dp[k] = max(dp[k], dp[k - i] + w[i][j]); } } } cout << *max_element(dp, dp + s + 1) << '\n'; return 0; }