#include <bits/stdc++.h> using namespace std; int main() { 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++) { for (long long j=s;j>=w[i];j--) { dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } } cout<<dp[s]<<"\n"; }