#include<bits/stdc++.h> #define int long long using namespace std; vector<int> f[3005]; int n, dp[3005]; void add(int v, int w, int k) { if(k == 0) return; int num = (k+1)/2; if(w*num <= n) f[w*num].push_back(v*num); add(v, w, k/2); } void add_object(int w, int v) { for(int i = n; i >= w; i--) dp[i] = max(dp[i], dp[i-w] + v); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int m; cin>>n>>m; for(int i = 1; i <= m; i++){ int v, w, k; cin>>v>>w>>k; add(v, w, k); } for(int i = 1; i <= n; i++){ sort(f[i].begin(), f[i].end(), greater<int>()); while(f[i].size() > n/i) f[i].pop_back(); } for(int i = 1; i <= n; i++){ for(int j : f[i]) add_object(i, j); } int ans = 0; for(int i = 0; i <= n; i++) ans = max(ans, dp[i]); cout<<ans; }