#include <bits/stdc++.h> #define int long long #define nn '\n' using namespace std; signed main() { int s , n; cin >> s >> n ; vector<int> v(n + 1) , w(n + 1) , k(n + 1); vector<int> dp(s + 1 , 0) , tenge(n + 1 , 0); dp[0] = 0; for(int i = 1; i <= n ; i++) { cin >> v[i] >> w[i] >> k[i]; } for(int i = 1; i <= n; i++) { for(int j = s ; j >= w[i] ; j--) { dp[j] = max(dp[j] , dp[j - w[i]] + v[i]); } } cout << dp[s] ; }