#include <bits/stdc++.h>
using namespace std;
using ll = long long;
signed main() {
ll size, n;
cin >> size >> n;
vector <ll> dp(size+1, 0), weights_res[size+1];
vector <pair<ll,ll>> weights[size+1];
for(ll i = 0; i<n; i++) {
ll value, weight, copy;
cin >> value >> weight >> copy;
weights[weight].push_back({value, copy});
}
for(ll i = 1; i<=size; i++) {
sort(weights[i].begin(), weights[i].end());
reverse(weights[i].begin(), weights[i].end());
}
for(ll i = 1; i <= size; i++) {
ll cnt = 0;
for(auto j : weights[i]) {
for(ll k = 0; k < j.second; k++) {
if(cnt > (2000+i-1)/i) goto here;
weights_res[i].push_back(j.first);
cnt++;
}
}
here:;
}
for(ll i = 1; i<=size; i++) { //weights
for(ll j : weights_res[i]) { // values
for(ll k = size; k >= 0; k--) {
dp[k] = max(dp[max(0ll, k-1)], dp[k]);
if(k + i <= size) dp[k+i] = max(dp[k] + j, dp[k+i]);
}
}
}
cout << dp[size];
return 0;
}
