#include<iostream>
using namespace std;
const int N=100005;
int m,n;
int number[N],w[N],space[N];
int v[N],worth[N];
int DP[N];
string name[N];
int main()
{
	cin>>m>>n;
	m=21-m;
	int cnt=1;
	for(int i=1;i<=n;i++)
	{
		cin>>number[cnt]>>w[cnt]>>space[cnt]>>name[cnt];
		for(int j=1;j<i;j++)
		{
			if(name[cnt]==name[j])
			{

				number[j]+=number[i];
				cnt--;
				break; 
			}
		}
		cnt++; 
	}
	cnt--; // 最后多加了一个记得删除 
	int num=0;
	for(int i=1;i<=cnt;i++)
	{
		while(number[i]>space[i])
		{
			num++;
			number[i]-=space[i];
			v[num]=space[i];
			worth[num]=w[i]*v[num];
		}
		if(number[i]>0)
		{
			num++;
			v[num]=number[i];
			worth[num]=w[i]*v[num];
		}
		
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=1;j--)
		{
			DP[j]=max(DP[j],DP[j-1]+worth[i]);
		}
	}
	if(m==0)
	{
		cout<<0;
		return 0;
	}
	cout<<DP[m];
	return 0;
}