#include<bits/stdc++.h>
#include<vector>
#include<unordered_map>
using namespace std;

const int N = 110;
int a[N], b[N], c[N], f[N][N]; 
unordered_map <string, int> ha;
int main()
{
    int m, n;
    cin >> m >> n;
    for(int i = 1 ; i <= n ; i ++)
    {
    	int ai,bi,ci;
    	string s;
    	cin >> ai >> bi >> ci >> s;    
		if(ha.count(s))
			a[ha[s]] += ai, n --, i --;	
		else
			ha[s] = i, a[i] = ai, b[i] = bi, c[i] = ci;
	}

    //dp
    for(int i = 1 ; i <= n ; i ++)
		for(int j = 1 ; j <= 21-m ; j ++)
		{
			if(f[i-1][j-1] + min(a[i], c[i]) * b[i] > f[i-1][j])
			{
				f[i][j] = f[i-1][j-1] + min(a[i], c[i]) * b[i];
				a[i] = abs(a[i] - c[i]);
			}
			else	f[i][j] = f[i-1][j];			
		}
		
	cout << f[n][21-m];
}