#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Item {
int value, number;
bool operator< (Item other) {
return value > other.value;
}
};
int maxKilo, nbItems;
vector<Item> items[2010];
int dp[2010][2010], maxPrice[2010];
int returnPrice(int poids, int poidsPanier) {
int iObjet = dp[poidsPanier][poids]+1;
int iType = 0;
if(iType >= items[poids].size()) {
return -2e16;
}
while(iObjet > items[poids][iType].number) {
iObjet -= items[poids][iType].number;
iType++;
if(iType >= items[poids].size()) {
return -2e16;
}
}
return items[poids][iType].value;
}
signed main() {
//ios_base::sync_with_stdio(false);
//cin.tie(0);
cin >> maxKilo >> nbItems;
for(int loop = 0; loop < nbItems; ++loop) {
int val, wei, nb;
cin >> val >> wei >> nb;
items[wei].push_back({val, nb});
}
for(int loop = 0; loop <= maxKilo; ++loop) {
sort(items[loop].begin(), items[loop].end());
}
for(int loop = 1; loop <= maxKilo; ++loop) {
int maxi = 0, posMaxi = -1;
for(int looping = 0; looping < loop; ++looping) {
int ajout = returnPrice(loop-looping, looping);
if(ajout + maxPrice[looping] >= maxi) {
maxi = ajout + maxPrice[looping];
posMaxi = looping;
}
}
for(int looping = 0; looping <= maxKilo; ++looping) {
dp[loop][looping] = dp[posMaxi][looping];
}
dp[loop][loop-posMaxi]++;
maxPrice[loop] = maxi;
}
int maxi = 0;
for(int loop = 0; loop <= maxKilo; ++loop) {
maxi = max(maxi, maxPrice[loop]);
}
cout << maxi << '\n';
}
