#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int,int>; #define FOR(i,a,b) for (int i=(a); i<=(b); ++i) #define FORD(i,a,b) for (int i=(a); i>=(b); --i) #define pb push_back const int INF = 1e9; const int MOD = 998244353; const ll MOD2 = 1e9 + 7; const ll LL_INF = 4e18; const int MAXN = 1e6 + 1; void solve() { int s, n; cin >> s >> n; vector<pair<ll,ll>> knapsack; //Chứa khối lượng & giá trị for (int i = 1; i <= n; i++) { ll v, w, k; cin >> v >> w >> k; if (k & 1) { knapsack.push_back({w, v}); k--; } else { knapsack.push_back({w,v}); knapsack.push_back({w,v}); k -= 2; } while (k) { if (k & 1) { knapsack.push_back({w,v}); } w *= 2; v *= 2; k /= 2; } } vector<ll> dp(s + 1, 0); for (auto [w, v] : knapsack) { for (int i = s; i >= w; i--) { dp[i] = max(dp[i], dp[i-w] + v); } } cout << dp[s] << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // preprocess(); int TC = 1; // cin >> TC; while (TC--) solve(); return 0; }