import java.io.*;
import java.math.*;
import java.util.*;
public class Main {
	static int idx,n,m,res,flag;
	static int[] w=new int[150000];
	static int[] f=new int[150000];
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StreamTokenizer st = new StreamTokenizer(br);
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) throws IOException {
		st.nextToken();m=(int)st.nval;
		m=21-m;
		st.nextToken();n=(int)st.nval;
		List<Person> list=new ArrayList<>();
		while(n-->0) {
			st.nextToken();int num=(int)st.nval;
			st.nextToken();int value=(int)st.nval;
			st.nextToken();int volume=(int)st.nval;
			st.nextToken();String name=st.sval;
			boolean b=false;
			for (int i = 0; i < list.size(); i++) {
				Person p=list.get(i);
				if (p.name.equals(name)) {
					p.num+=num;
					b=true;
					break;
				}
			}
			if (!b) {
				list.add(new Person(name, num, value, volume));
			}
		}
		for (int i = 0; i < list.size(); i++) {
			Person p=list.get(i);
			int num=p.num,value=p.value,volume=p.volume;
			while(num>volume) {
				num-=volume;
				w[++idx]=value*volume;
			}
			w[++idx]=value*num;
		}
		for (int i = 1; i <= idx; i++) {
			for (int j = m; j >= 1; j--) {
				f[j]=Math.max(f[j], f[j-1]+w[i]);
			}
		}
		System.out.println(f[m]);
	}
}
class Person{
	String name;
	int num,value,volume;
	/**
	 * @param name
	 * @param num
	 * @param value
	 * @param volume
	 */
	public Person(String name, int num, int value, int volume) {
		super();
		this.name = name;
		this.num = num;
		this.value = value;
		this.volume = volume;
	}
	
}