#include<bits/stdc++.h>
using namespace std;
typedef vector<long long int> vi;
typedef vector<vi> vvi;
vvi dp;
vi values, weight, freqs;
int S, N;
int main(){
cin >> S >> N;
dp = vvi(S+1, vi(S+1, 0));
values = vi(N);
weight = vi(N);
freqs = vi(N);
vector<vector<pair<int, int>>> itemsWithWeight(S+1);
for(int i = 0; i < N; ++i) {
cin >> values[i] >> weight[i] >> freqs[i];
itemsWithWeight[weight[i]].push_back({values[i], freqs[i]});
}
//cout << "a" << endl;
for(int i = 0; i <=S; ++i)sort(itemsWithWeight[i].rbegin(), itemsWithWeight[i].rend());
//cout << "a" << endl;
long long int ans = 0;
for(int i = 1; i <= S; ++i){
for(int weight = 0; weight <= S; ++weight){
int accumulatedWeight = 0;
int accumulatedValue = 0;
dp[weight][i] = dp[weight][i-1];
ans = max(ans, dp[weight][i]);
for(pair<int, int> item: itemsWithWeight[i]){
int myVal = item.first;
int reps = item.second;
for(int rep = 0; rep < reps; ++rep){
accumulatedWeight += i;
accumulatedValue += myVal;
if(accumulatedWeight > weight) break;
dp[weight][i] = max(dp[weight][i], dp[weight - accumulatedWeight][i-1] + accumulatedValue);
ans = max(ans, dp[weight][i]);
}
if(accumulatedWeight > weight) break;
}
}
}
cout << ans << endl;
return 0;
}
