#include <bits/stdc++.h> using namespace std; #define ll long long #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define el '\n' const int NMAX = 2005; ll dp[NMAX]; int main() { fast; int S,n; cin >> S >> n; for(int i=0;i<n;i++) { ll v,w,k; cin >> v >> w >> k; ll c=1; while(k>0) { ll t=min(c,k); ll val=v*t; ll wei=w*t; for(int j=S;j>=wei;j--) dp[j]=max(dp[j], dp[j-wei]+val); k-=t; c<<=1; } } cout << dp[S] << el; return 0; }