#pragma GCC optimize("O5,unroll-loops,inline,fast-math") #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") #include <bits/stdc++.h> #define exoworldgd cin.tie(0)->sync_with_stdio(0), cout.tie(0) #define int long long #define pii pair<int,int> using namespace std; const int N=2005,M=1e9+7,inf=1e18; int s,n,dp[N],sz=0; pii v[3000005]; signed main(void) { exoworldgd; cin >> s >> n, memset(dp,0,sizeof dp); for (int i=0,x,w,k,cnt; i<n; i++) { cin >> x >> w >> k,cnt=1; while (k>0) v[sz++]={w*min(cnt,k),x*min(cnt,k)}, k-=min(cnt,k), cnt<<=1; } for (int i=0; i<sz; i++) for (int j=s; j>=v[i].first; j--) dp[j]=max(dp[j],dp[j-v[i].first]+v[i].second); cout << dp[s]; }