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