#include <bits/stdc++.h> using namespace std; int main() { //freopen("1.in","r",stdin); long long s,n; cin>>s>>n; vector<long long> v(n), w(n), k(n); for (long long i=0;i<n;i++) cin>>v[i]>>w[i]>>k[i]; vector<long long> dp(s+1,0); for (long long i=0;i<n;i++) { for (long long m=0;m<k[i];m++) { bool flag=false; for (long long j=s;j>=w[i];j--) { long long temp=dp[j-w[i]]+v[i]; if (temp>dp[j]) { dp[j]=temp; flag=true; } } if (!flag) break; } // for (auto num:dp) cout<<num<<" "; // cout<<"\n"; } cout<<dp[s]<<"\n"; }