#include<bits/stdc++.h>
using namespace std;
int n,M,n1,i,j,k,w[100001],v[100001],dp[30],p[200];
struct node
{
	int a,b,c,g;
	string s;
}f[200];
int main()
{
	cin>>M>>n;
	M=21-M;
	for(i=1;i<=n;i++)
		cin>>f[i].a>>f[i].b>>f[i].c>>f[i].s;
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
			if(f[i].s==f[j].s)
			{
				f[i].a+=f[j].a;
				p[j]=1;
			}
	for(i=1;i<=n;i++)
		if(p[i]!=1)
		{
			f[i].g=f[i].a/f[i].c;
			if(f[i].a%f[i].c!=0)
				f[i].g++;
		}
	for(i=1;i<=n;i++)
		if(p[i]!=1)
		{
			int t=1,s=f[i].g;
			while(s>=t)
			{
				v[++n1]=f[i].b*f[i].c*t;
				w[n1]=t;
				s-=t;
				t*=2;
			}
			if(s!=0)
			{
				v[++n1]=f[i].b*f[i].c*t;
				w[n1]=t;
			}
		}
	for(i=1;i<=n1;i++)
		for(j=M;j>=w[i];j--)
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    cout<<dp[M];
}