// #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<ll> d(s+1,-inf); d[0] = 0; for (auto &[w,q] : a) { sort(q.rbegin(),q.rend()); for (int i=s; i>=0; i--) { ll p = 0, r = 0; for (auto [v,k] : q) for (int l = 0; l<k && p<i/w; l++,p++,r+=v) if (d[i-(p+1)*w]!=-inf) d[i] = max(d[i],d[i-(p+1)*w]+r+v); } } ll res = *max_element(d.begin(),d.end()); cout << res << "\n"; }