#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 1000001
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
struct data{
    int a,b,c;
    bool vis;
    string s;
}t[maxn];

int v[maxn],f[maxn];
int n,m,js;
int main()
{
    m=read(); n=read();
    for(int i=1;i<=n;i++){
        t[i].a=read(); t[i].b=read(); t[i].c=read(); cin>>t[i].s;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(t[i].s==t[j].s){
                 t[i].a+=t[j].a; t[j].vis=true;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(t[i].vis==true) continue;
        if(t[i].c>=t[i].a){
            v[++js]=t[i].b*t[i].a;
        }else{
            while(t[i].a>t[i].c){
                t[i].a-=t[i].c; v[++js]=t[i].b*t[i].c;
            }
            v[++js]=t[i].a%t[i].c*t[i].b;
        }
    }
    for(int i=1;i<=js;i++){
        for(int j=21-m;j>=0;j--){
            f[i]=max(f[i-1],f[i-1]+v[i]);
        }
    }
    cout<<f[21-m];
    return 0;
}