#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
const int N = 2000 + 5;
vector<pair<int, int> > vec[N], nw;
int dp[2000 * 15][N];
int main(){
int s, n; cin >> s >> n;
int val, w, r;
for(int i = 1; i <= n; i++){
cin>>val>>w>>r;
vec[w].push_back({val, r});
}
for(int i = 1; i <= s; i++){
sort(vec[i].begin(), vec[i].end());
reverse(vec[i].begin(), vec[i].end());
int tot = s / i;
for(int j = 0; j < (int)vec[i].size(); j++){
int raod = vec[i][j].second;
int value = vec[i][j].first;
if (raod <= tot){
for(int z = 1; z <= raod; z++){
nw.push_back({i, value});
}
tot -= raod;
} else {
for(int z = 1; z <= tot; z++){
nw.push_back({i, value});
}
tot = 0;
break;
}
}
}
// dp[i][j] pirveli i cali nivti, j aris wona = maximaluri value
n = nw.size();
int ans = 0;
for(int i = 1; i <= n; i++){
int wona = nw[i - 1].first;
int value = nw[i - 1].second;
for(int j = 0; j <= s; j++){
dp[i][j] = dp[i-1][j];
if (j >= wona) dp[i][j] = max(dp[i][j], dp[i-1][j-wona]+value);
ans = max(ans, dp[i][j]);
}
}
cout<<ans<<endl;
}
