点2，5

#include<bits/stdc++.h>
using namespace std;
int dp[1000001];
int a[101],b[101],c[101];
int n,m;
string sti[101];
int _left;
map<string, int> dict;

int check(int x, int y)
{
	if(x%y==0) return x/y;
	else return x/y+1;
}

int main()
{
	cin>>m>>n;
	_left=21-m;
	for(int i=1; i<=n; i++)
	{
		cin>>a[i]>>b[i]>>c[i]>>sti[i];
		if(dict[sti[i]]!=0)
		{
			a[dict[sti[i]]]+=a[i];
			if(a[dict[sti[i]]]>c[i])
			{
				a[i]=a[dict[sti[i]]]-c[i];
				a[dict[sti[i]]]=c[i];

			}
			else a[i]=0;
		}
		else
		{
			dict[sti[i]]=i;
		}
	} 

	memset(dp,-1,sizeof(dp));
	dp[0]=0;

	for(int i=1; i<=n; i++)
	{
		for(int j=0; j<=_left; j++)
		{
			for(int k=1; k<=a[i]; k++)
			{
				if(dp[j]!=-1 && check(k,c[i])+j<=_left)
				{
					dp[check(k,c[i])+j]=max(dp[check(k,c[i])+j], dp[j]+k*b[i]);
				}
			}
		}
	}
	int ans=-1;
	for(int i=0; i<=_left; i++)
		ans=max(ans,dp[i]);
	cout<<ans;
	return 0;
}