/* * * author: attacker * * created: 27.01.2026 16:54:50 */ #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif #define mt_rng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; int64_t lim; cin >> lim >> n; vector<int64_t> v(n); vector<int64_t> w(n); for (int i = 0; i < n; i++) { cin >> v[i] >> w[i]; int a; cin >> a; } const int64_t inf = int64_t(1e18); vector<int64_t> dp(lim + 1, -inf); dp[0] = 0; for (int i = 0; i < n; i++) { for (int64_t j = lim; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } cout << dp[lim] << '\n'; return 0; }