import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashMap;
import java.util.Map;

/**
 * P1964 【mc生存】卖东西
 */
public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int in() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    static String in2() throws IOException {
        in.nextToken();
        return in.sval;
    }

    public static void main(String[] args) throws IOException {
        int m = 21 - in();
        int n = in();
        Map<String, Integer> map = new HashMap<>();
        int[] ai = new int[n + 1];
        int[] bi = new int[n + 1];
        int[] ci = new int[n + 1];
        int cnt = 1;
        for (int i = 1; i <= n; i++) {
            int a = in();
            int b = in();
            int c = in();
            String sti = in2();
            if(map.containsKey(sti)) {
                ai[map.get(sti)] += a;
            } else {
                ai[cnt] = a;
                bi[cnt] = b;
                ci[cnt] = c;
                map.put(sti, cnt);
                ++cnt;
            }
        }
        n = cnt - 1;
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= ai[i]; k++) {
                    int v = k % ci[i] == 0 ? k / ci[i] : k / ci[i] + 1;
                    if(j >= v) {
                        f[i][j] = Math.max(f[i][j], f[i - 1][j - v] + k * bi[i]);
                    }
                }
            }
        }
        System.out.println(f[n][m]);
    }
}