//#ifndef khos //#pragma GCC optimize ("Ofast") //#pragma GCC optimize ("unroll-loops") //#endif #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #ifdef khos #include "t_debug.cpp" #else #define debug(...) 42 #endif using namespace std; using namespace __gnu_pbds; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T> using indexed_multiset = tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>; #define int int64_t #define vi vector #define ss second #define ff first #define TESTCASES #define all(x) (x).begin(), (x).end() const int mod = 1e9+7; const int MAXN=2000000+5; const int inf=1e18; void solution() { int n, s; cin >> s >> n; vi<int> v(n), w(n), k(n); for(int i=0; i<n; i++){ cin >> v[i] >> w[i] >> k[i]; } vi<int> dp(s+10); for(int i=0; i<n; i++){ while(k[i]>0){ int c=1; int mn=min(c, k[i]); int val=mn*w[i]; for(int j=s; j>=val; j--){ if(j==val)dp[j]=max(dp[j], v[i]*mn); else { if(dp[j-val])dp[j]=max(dp[j], dp[j-val]+v[i]*mn); } } k[i]-=mn; c<<=1; } } int mx=0; for(int i=0; i<=s; i++)mx=max(mx, dp[i]); cout << mx; } int32_t main(){ clock_t tStart = clock(); #ifdef khos freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int q = 1; #ifdef TESTCASES // cin >> q; #endif while(q--) { solution(); cout << '\n'; } cerr<<fixed<<setprecision(3)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl; }