#include <iostream> using namespace std; int f[105][1005]; int w[1005], c[1005]; int z[105][1005]; int sumz = 0; int main() { int m, n; cin >> m >> n; for (int i = 1, _z; i <= n; i++) { cin >> w[i] >> c[i] >> _z; if (!z[_z][0]) sumz++; z[_z][++z[_z][0]] = i; } for (int i = 1; i <= sumz; i++) { for (int j = 1; j <= m; j++) { f[i][j] = f[i - 1][j]; for (int k = 1; k <= z[i][0]; k++) { if (j >= w[z[i][k]]) { f[i][j] = max(f[i][j], f[i - 1][j - w[z[i][k]]] + c[z[i][k]]); } } } } cout << f[sumz][m]; }