// #pragma GCC optimize("Ofast,unroll-loops") // #pragma GCC target("avx,avx2,fma") #include "bits/stdc++.h" #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; using ll = long long; using ld = long double; using ui = unsigned int; using ul = unsigned long long; using i128 = __int128; using pii = pair<int, int>; using pll = pair<ll, ll>; using t3i = tuple<int, int, int>; using t3l = tuple<ll, ll, ll>; using vi = vector<int>; using vl = vector<long long>; using vb = vector<bool>; using vp = vector<pair<ll, ll>>; using arr = array<int, 4>; using node = pair<int, arr>; template <class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const ll inf = 1e18; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int s, n; cin >> s >> n; map<int, vp> a; for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; a[w].push_back({v,k}); } vector<vl> d(a.size()+1,vl(s+1,-inf)); d[0][0] = 0; int i = 1; for (auto &[w,q] : a) { sort(q.rbegin(),q.rend()); for (int j = 0; j <= s; j++) { ll p = 0, r = 0; d[i][j] = d[i-1][j]; for (auto [v,k] : q) for (int l = 0; l < k && p<=j/w; l++) { p += 1, r += v; if (p<=j/w && d[i-1][j-p*w]!=-inf) d[i][j] = max(d[i][j],d[i-1][j-p*w]+r); } } i += 1; } ll res = -inf; for (int i = 0; i <= s; i++) res = max(res,d[a.size()][i]); cout << res << "\n"; }