#include <fstream>
#include <string>
#include <iostream>
using namespace std;

long m, n, i, j, pts, length;
long best[3000000];
string a;
long super;
bool used[3000000];

int main() {
	ifstream fin("DATA3.txt");
	ofstream fout(	"OUT3.txt");
	
	for (long xj=0; xj<5; xj++) {
	fin >> m >> n;

	for (i = 0; i<n; i++) {
		fin >> a >> pts >> length;

		memset(used, false, sizeof(used));
		for (j=0; j+length<=m; j++)
			if (!used[j])
				if (best[j] + pts > best[j+length]) {
					best[j+length] = best[j] + pts;
					used[j+length] = true;
				}
	}

	cout << best[m] << endl;
	}
	return 0;
}