import java.io.*;
import java.util.*;

public class Main {

    private static class Good {
        int v;
        int w;

        public Good(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        int N = Integer.parseInt(s1[0]);
        int M = Integer.parseInt(s1[1]);
        Good[] master = new Good[N + 1];
        List<Good>[] servent = new ArrayList[N + 1];
        for (int i = 1; i <= M; i++) {
            String[] s2 = br.readLine().split(" ");
            int v = Integer.parseInt(s2[0]);
            int p = Integer.parseInt(s2[1]);
            int q = Integer.parseInt(s2[2]);
            if (q == 0) {
                master[i] = new Good(v, v * p);
                servent[i] = new ArrayList<>();
            } else
                servent[q].add(new Good(v, v * p));
        }
        int[] dp = new int[N + 1];
        for (int i = 0; i < master.length; i++) {
            if (master[i] == null)
                continue;
            for (int j = N; j >= 0; j--) {
                for (int k = 0; k < (1 << servent[i].size()); k++) {
                    int v = master[i].v;
                    int w = master[i].w;
                    for (int t = 0; t < servent[i].size(); t++) {
                        if (((k >> t) & 1) == 1) {
                            v += servent[i].get(t).v;
                            w += servent[i].get(t).w;
                        }
                    }
                    if (j >= v)
                        dp[j] = Math.max(dp[j], dp[j - v] + w);
                }
            }
        }
        System.out.print(dp[N]);
    }
}