#include <bits/stdc++.h> using namespace std; int helper(vector<vector<int>>&dp,int i,int w,int n,vector<int>&values,vector<int>&weights){ if(w == 0){ return 0; } if( i == n) return 0; if(dp[i][w] != -1) return dp[i][w]; int a = helper(dp,i+1,w,n,values,weights); int b = w >= weights[i] ? helper(dp,i+1,w - weights[i],n,values,weights) + values[i]: 0; return dp[i][w] = max(a,b); } int main() { // your code goes here int n,s; cin>>s>>n; vector<int>w(n),v(n),k(n); int sum = 0; vector<int>values,weights; for(int i=0;i<n;i++){ cin>>v[i]>>w[i]>>k[i]; int sum = 0; for(int j=0;j<32;j++){ if(sum + (1<<j) > k[i]){ values.push_back(v[i]*(k[i]-sum)); weights.push_back(w[i]*(k[i]-sum)); break; } sum += (1<<j); values.push_back(v[i]*(1<<j)); weights.push_back(w[i]*(1<<j)); } } int ans = 0; int m = values.size(); vector<vector<int>>dp(m,vector<int>(s + 1,-1)); cout<<helper(dp,0,s,m,values,weights); }