#include<bits/stdc++.h> using namespace std; #define pb push_back #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define srt(x) sort(all(x)) #define rev(x) reverse(all(x)) #define rsrt(x) sort(rall(x)) #define sz(x) (int)x.size() #define fi first #define se second #define lsb(x) x&(-x) #define gcd(a,b) __gcd(a,b) using ll = long long; using ld = long double; using ull = unsigned long long; using pll = pair<ll, ll>; using vll = vector<ll>; using vpll = vector<pll>; using vvll = vector<vll>; const ll inf=1e18; int main(){ ios::sync_with_stdio(0); cin.tie(0); ll s, n; cin>>s>>n; map<int, vector<pair<int, int>>> by_w; for(int i=0; i<n; i++){ int v, w, k; cin>>v>>w>>k; by_w[w].pb({v, k}); } vll dp(s+1); for(auto &[w, items] : by_w){ rsrt(items); for(int j=s; j>=w; j--){ int c = 0, type = 0, used = 0; ll profit = 0; while((c+1)*w <= j && type < sz(items)){ c++; profit += items[type].first; dp[j] = max(dp[j], dp[j-c*w]+ profit); used++; if(used == items[type].second){ type++; used = 0; } } } } cout<<dp[s]<<'\n'; }