#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++) { long long lastdjs=dp[s]; for (long long j=s;j>=w[i];j--) { dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } if (lastdjs==dp[s]) break; } } cout<<dp[s]<<"\n"; }