#include<bits/stdc++.h>
using namespace std;
struct node{
    int a, b, c;
    string na;
}thing[1005];

int f[100];
int main() {
    int m, n;
    scanf("%d%d", &m, &n);
    int maxn = 21 - m;
    int n1 = 0;
    for (int i = 1; i <= n; i++) {
        int a, b, c;
        char st[105];
        scanf("%d%d%d%s", &a, &b, &c, st);
        int judge = 0;
        if (n1 == 0) {
            n1++;
            thing[n1].a = a;
            thing[n1].b = b;
            thing[n1].c = c;
            thing[n1].na = st;
        } else {
            for (int j = 1; j <= n1; j++) {
                if (thing[j].na == st) {
                    thing[j].a += a;
                    judge = 1;
                    break;
                }
            }
            if (!judge) {
                n1++;
                thing[n1].a = a;
                thing[n1].b = b;
                thing[n1].c = c;
                thing[n1].na = st;
            }
        }
    }
    for(int i=1;i<=n1;i++){
    	if(thing[i].c>thing[i].a){
    		n1++;
    		thing[n1].a = thing[i].a;
            thing[n1].b = thing[i].b;
            thing[n1].c = thing[i].c-thing[i].a;
            thing[n1].na = thing[i].na;
            thing[i].c = thing[i].a;
		}
	}
    for (int i = 1; i <= n1; i++) {
        for (int j = maxn; j >= 0; j--) {
            for (int k = 0; k <= j && k <= thing[i].a; k++) {
                f[j] = max(f[j], (j >= k * thing[i].b ? f[j - k * thing[i].b] + k * thing[i].c : 0));
            }
        }
    }
    printf("%d", f[maxn]);
    return 0;
}