#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<pair<int, int>> dv; dv.reserve(n); for(int i = 0; i < n; i++) { int v, w, k; cin>>v>>w>>k; for(int b = 1; b <= k; b <<= 1) { dv.emplace_back(w * b, v * b); k -= b; } if(k > 0) dv.emplace_back(w * k, v * k); } vector<int> dp(s + 1, 0); for(auto &it : dv) { int w = it.first; int v = it.second; for(int x = s; x >= w; x--) dp[x] = max(dp[x], dp[x - w] + v); } cout<<dp[s]; return 0; }