#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
struct Item{
ll v, k;
};
void solve(){
int s,n;
cin >> s >> n;
vector <vector <Item>> l1(s+1);
for (int i = 0; i < n; i++){
ll v,w,k;
cin >> v >> w >> k;
l1[w].push_back({v,k});
}
vector <vector <ll>> final(s+1);
for (int i = 1; i <= s; i++){
sort(l1[i].begin(), l1[i].end(), [](Item &a, Item &b){
return a.v > b.v;
});
int counter = 0;
int cur = 0;
for (int j = 0; j < (int)l1[i].size(); j++){
while (cur < l1[i][j].k && counter < (s/i)){
counter += 1;
cur += 1;
final[i].push_back(l1[i][j].v);
}
cur = 0;
}
}
vector <ll> dp(s+1,0);
for (int i = 1; i <= s; i++){
for (auto &p : final[i]){
for (int j = s; j >= i; j--){
dp[j] = max(dp[j],dp[j-i] + p);
}
}
}
cout << dp[s] << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
