#include <bits/stdc++.h> #define int long long using namespace std; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int s, n; cin >> s >> n; vector<int> dp(s + 1, 0); while(n--) { int v, w, k; cin >> v >> w >> k; if(w > s) continue; int maxx = s / w; if(k > maxx) k = maxx; for(int p = 1; k > 0; p <<= 1) { int t = min(p, k); k -= t; int x = t * w; int val = t * v; for(int j = s; j >= x; j--) dp[j] = max(dp[j], dp[j - x] + val); } } cout << dp[s]; return 0; }