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

int lim, n, maxi;
int space[110], rat[110];

void go(int curspace, string check, int currat) {
	if (currat > maxi)
		maxi = currat;
	int i;
	for (i = 0; i < n; i++) {
		if (check[i] == '0') {
			if (curspace + space[i] <= lim) {
				check[i] = '1';
				go(curspace + space[i], check, currat + rat[i]);
				check[i] = '0';
			}
		}
	}
	return;
}

int main() {
	ifstream filein("DATA3.txt");
	ofstream fileout("OUT3.txt");
	
	for (int zzz = 0; zzz < 5; zzz++) {
	maxi = 0;

	int i;
	string temp, s;

	filein >> lim;
	filein >> n;
	for (i = 0; i < n; i++) {
		filein >> s >> rat[i] >> space[i];
		temp += '0';
	}

	go(0, temp, 0);

	fileout << maxi << endl;
		
	}

	filein.close();
	fileout.close();
	return(0);
}