#include<iostream> #include<vector> #include<algorithm> using namespace std; const int MAXN = 1005; int main() { int m, n, k; cin >> m >> n; vector<int> weight(n + 1), value(n + 1), group(n + 1); for(int i = 1; i <= n; ++i){ cin >> weight[i] >> value[i] >> group[i]; } vector<int> dp(m + 1, 0); for(int i = 1; i <= n; ++i){ if(i > 1 && group[i] == group[i - 1]) continue; for(int j = m; j >= 0; --j){ for(int k = i; k <= n; ++k){ if (group[k] != group[i]) break; if(j >= weight[k]){ dp[j] = max(dp[j], dp[j - weight[k]] + value[k]); } } } } cout << dp[m] << endl; return 0; }