#include <iostream>
#include <cstdio>
#include <map>
#include <vector>

using namespace std;
using ll = long long;

const int N = 2025;

int main(/*void*/)
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, V;
    cin >> V >> n;
    int a[N] /*重量*/, b[N] /*价值*/, c[N] /*第几组*/;
    map<int, vector<pair<int, int>>> mp;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i] >> c[i];
        mp[c[i]].push_back({a[i], b[i]});
    }
    int k = mp.size(); // 组数
    int dp[N] = {0};   // dp[v]重量为v时的最大价值
    for (int i = 1; i <= k; i++)
    {
        for (int v = V; v >= 1; v--)
        {
            for (int j = 0; j < mp[i].size(); j++)
            {
                if (j >= mp[i][j].first)
                    dp[j] = max(dp[j], dp[j - mp[i][j].first] + mp[i][j].second);
            }
        }
    }
    cout << dp[V] << endl;
    return 0;
}