#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); for(int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; for(int dem = 1; k > 0; dem <<= 1) { int lay = min(dem, k); k -= lay; int t = w * lay; int val = v * lay; if(t > s) continue; for(int x = s; x >= t; x--) dp[x] = max(dp[x], dp[x - t] + val); } } cout << dp[s]; return 0; }