#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #ifdef LOC #include"debug_functions.h" #endif using namespace std; using namespace __gnu_pbds; #define sync #define LLFORCe #define ll long long #ifdef LLFORCe #define int long long #endif //#define ll int #define forn(i,n) for(ll i=0;i<n;i++) #define rep(i,a,b) for(ll i=a;i<=b;++i) #define per(i,a,b) for(ll i=a;i>=b;--i) #define all(v) v.begin(), v.end() #define lze(x) __builtin_clz(x) #define tze(x) __builtin_ctz(x) // 'bit' below means bit position #define msb(mask) (63-__builtin_clzll(mask*1ll)) //highest set bit #define lsb(mask) __builtin_ctzll(mask*1ll) // lowest set bit #define cntsetbits(mask) __builtin_popcountll(mask*1ll) //number of bits #define checkbit(mask,bit) ((mask >> bit) & 1ll) #define onbit(mask,bit) ((mask)|(1LL<<(bit))) //turns mask's bit position (=bit) on #define offbit(mask,bit) ((mask)&(~(1LL<<(bit)))) //turns mask's bit position (=bit) off #define flipbit(mask,bit) ((mask)^(1LL<<bit)) //flips mask's bit position (=bit) #define nnn continue #define fff fflush(stdout) #define limit(x,a,b) ((a)<=(x) && (x)<=(b)) #define gt(arr,i) (((limit(i,0,(ll)((arr).size())-1))?(arr)[i]:decltype((arr)[0]){})) #define gt2d(arr,i,j) (((limit(i,0,(ll)((arr).size())-1)) && (limit(j,0,(ll)((arr[i]).size())-1))?(arr)[i][j]:decltype((arr)[0][0]){})) using pii=pair<ll,ll>; using ints=vector<ll>; using chars=vector<char>; using cntmap=map<ll,ll>; using ipairs=vector<pair<ll,ll>>; using cpairs=vector<pair<char,char>>; using arr2d=vector<ints>; using cmatrix=vector<chars>; template<typename T> using minpq=priority_queue<T,vector<T>,greater<T>>; //min to max template<typename T> using maxpq=priority_queue<T>; //max to min // for descending order replace less<int> with greater<int> typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset; // ordered multiset typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> omultiset; // usage: oset::find by order(i) <-- index of ith element as iterator, oset::order_of_key(x) <-- index of x (or number of elements <x, also works for elements which dont exist in oset) ll iabs(ll x){return (x>0)?x:-x;} ll dceil(ll a,ll b){return a/b+(a%b?1:0);} ll rmd(ll a,ll b){return ((a%b)+b)%b;} ll logn(ll n,ll a){ll c=0;while (n>=a){n/=a;c++;}return c;} ll sqr(ll a){return a*a;} ll powb(ll a, ll b, ll mod=LONG_LONG_MAX){ll p=1;a%=mod; for(ll j=0;(1ll<<j)<=b;++j){if((1ll<<j)&b){p*=a; p%=mod;} a*=a;a%=mod;} return p%mod;} // better to use (b>>j)&1 than (1ll<<j) ll bsqrt(ll n){ll l=0,h=n; while(h-l>1){ll m=l+(h-l)/2; if(m<=n/m) l=m;else h=m-1;} if(h*h<=n) return h;else return l;} ll mod=1e9+7; ll wtf=998244353; #ifdef LOC #define debug(x) cerr<<#x<<": ";_print(x);cerr<<"\n"; #else #define debug(x) #endif template<typename T,typename U>istream& operator>>(istream& in,pair<T,U>& p){in>>p.first>>p.second;return in;} template<typename T>void print(const vector<vector<T>>& arr){for(auto& x: arr){for(auto& y:x) cout<<y<<' ';cout<<'\n';}} template<typename T>void print(const vector<T>& arr){for(auto& x:arr){cout<<x<<' ';}cout<<'\n';} template<typename T,typename U>void print(const vector<pair<T,U>>& arr){for(auto& x:arr){cout<<x.first<<' ';}cout<<'\n';for(auto& x:arr){cout<<x.second<<' ';}cout<<'\n';} template<typename T,typename U>void print(const vector<pair<T,U>>& arr,bool oneachline){for(auto& x:arr) cout<<x.first<<' '<<x.second<<'\n';} template<typename T>void in(vector<T>& arr){for(auto& x:arr){cin>>x;}} template<typename T>void in(vector<vector<T>>& a){for(auto& x:a){in(x);}} template<typename T,typename U>void print(pair<T,U> p){cout<<p.first<<' '<<p.second<<'\n';} // put template code below this line ~~~ // If it feels hard, simplify it! signed main() { #ifdef sync ios_base::sync_with_stdio(0); cin.tie(0); #endif ll testcase=1; // cin>>testcase; while (testcase--) { int n,S;cin>>S>>n; arr2d a(n,ints(3)); in(a); ipairs wtv[S+1]{}; forn(i,n) { wtv[a[i][1]].push_back({a[i][0],a[i][2]}); } rep(w,0,S) { sort(all(wtv[w]),greater<pii>()); } int dp[S+2][S+2]{}; per(w,S,0) { rep(s,0,S) { dp[w][s]=dp[w+1][s]; int j=1;// count of the number of items taken with weight w int tot=0;// total value count of j items for(pii& vc:wtv[w]) { for(int i=1;i<=vc.second;++i) { tot+=vc.first; debug(j) debug(tot) if(s-w*j<0) goto done; debug(dp[w+1][s-w*j]+tot) dp[w][s]=max(dp[w][s],dp[w+1][s-w*j]+tot); j++; } } done:; } } // rep(w,0,S) // { // rep(s,0,S) cout<<dp[w][s]<<' ';cout<<"\n"; // } cout<<dp[0][S]<<"\n"; } }