#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[2005][2005];
int search(int i, int remW, vector<pair<int,int>>& kp, int total){
if (i == total) return 0;
if (remW == 0) return 0;
if (dp[i][remW] != -1) return dp[i][remW];
if (kp[i].first <= remW){
return dp[i][remW] = max(search(i+1,remW,kp,total),search(i+1,remW-kp[i].first,kp,total)+kp[i].second);
}
else{
return dp[i][remW] = search(i+1,remW,kp,total);
}
}
signed main() {
memset(dp,-1,sizeof(dp));
int s,n;
cin >> s >> n;
vector<pair<int,int>> arr[2000];//offset weight by one for now
for (int i = 0; i<n; i++){
int v,w,k;
cin >> v >> w >> k;
w--;
arr[w].push_back({v,k}); //value quantity
//k = min(2000,k);
//w--;
//int sz1 = arr[w].size();
//int left = min(2000-sz1,k);
//for (int j = 0; j<left; j++){
// arr[w].push_back(v);
//}
}
int total = 0;
vector<pair<int,int>> kp;
for (int i = 0; i<2000; i++){
sort(arr[i].begin(),arr[i].end());
reverse(arr[i].begin(),arr[i].end());
int lft = 2000;
int sz = arr[i].size();
int pt = 0;
while (lft > 0 && pt != sz){
int dec = min(lft,arr[i][pt].second);
lft -= dec;
for (int j = 0; j<dec; j++){
int val = arr[i][pt].first;
kp.push_back({i+1,val});
}
pt++;
}
total += 2000-lft;
//for (int j = 0; j<min(2000,sz); j++){
// kp.push_back({i+1,arr[i][j]}); //weight,value
//}
}
cout << search(0,s,kp,total) << '\n';
return 0;
}
