#include <iostream>
#include <vector>
#include<math.h>
using namespace std;
struct huowu {
	string name;
	int shenyu;
	int jiazhi;
	int ronglian;
}f[105];
int DP[105][25];
int main() {
	int m, n;
	cin >> m >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> f[i].shenyu >> f[i].jiazhi >> f[i].ronglian >> f[i].name;
	}
	int beibao = 21;
	int gezi = beibao - m;
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <=n; ++j) {
			if (f[i].name == f[j].name) {
				if (f[i].shenyu + f[j].shenyu >= f[i].ronglian) {
					f[i].shenyu = f[i].ronglian;
					f[j].shenyu = f[i].shenyu + f[j].shenyu - f[i].ronglian;
				}
				else {
					f[j].shenyu = 0;
					f[j].jiazhi = 0;
					f[j].ronglian= 0;
				}
			}
		}
	}
	DP[0][0] = 0; DP[0][1] = 0;
	for (int i = 1; i <=n; ++i) {
		for(int j=1;j<=gezi;++j){
		if (gezi > 0) {
			DP[i][j] =max(DP[i-1][j],DP[i-1][j-1]+f[i].shenyu*f[i].jiazhi);
		}
		else {
			DP[i][j] = DP[i - 1][j];
		}
		}
	}
	cout << DP[n][gezi];
}