#include<bits/stdc++.h>
#define int long long
using namespace std;
map<string,int> mp;
map<string,int> my;
vector<string> vc;
int wu[200010];
int ans;
int dp[200010];
signed main(){
	int m,n;
	cin>>m>>n;
	int sheng=21-m;
	int a,b,c;
	string s;
	for(int i=1;i<=n;i++){
		cin>>a>>b>>c>>s;
		if(mp[s]==0){
			vc.push_back(s);
		}
		mp[s]+=a;
		my[s]=b;
	}
	int cnt=0;
	for(int i=0;i<vc.size();i++){
		while(mp[vc[i]]>=64){
			cnt++;
			wu[cnt]=64*my[vc[i]];
			mp[vc[i]]--;
		}
		if(mp[vc[i]]>0){
			cnt++;
			wu[cnt]=mp[vc[i]]*my[vc[i]];
		}
	}
	for(int i=1;i<=cnt;i++){
		for(int j=sheng;j>=1;j--){
			dp[j]=max(dp[j],dp[j-1]+wu[i]);
		}
	}
	cout<<dp[sheng];
    return 0;
}