#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

const int MAXN = 1e4 + 10;
const int MAXM = 1e4 + 10;
struct Node {
    int a, b, c;
} bag[MAXN];
LL dp[MAXM];
int main() {
    int n, m;
    scanf("%d%d", &m, &n);
    
    for (int i = 0; i < n; i++) scanf("%d%d%d", &bag[i].a, &bag[i].b, &bag[i].c);

    sort(bag, bag + n, [](Node a, Node b) {
        if (a.c == b.c) {
            if (a.b == b.b) return a.a > b.a;
            return a.b > b.b;
        } else {
            return a.c < b.c;
        }
    });

    for (int i = 1; i <= n;) {
        int nxt = 0;
        for (int j = m; j >= 1; j--) {
            int mind = bag[i - 1].c;
            int k = 0;
            while (bag[i + k - 1].c == mind) {
                if (j >= bag[i + k - 1].a) dp[j] = max(dp[j], dp[j - bag[i + k - 1].a] + bag[i + k - 1].b);
                k++;
            }
            nxt = k;
        }
        i += (nxt + 1);
    }

    printf("%lld\n", dp[m]);
    return 0;
}

WA掉了3、5、6点