#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; int 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-(int)wei]+(int)val); k -= t; c <<= 1; } } cout << dp[S] << el; }