// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
#include <functional>
#include <utility>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int maxWeight, numItems;
cin >> maxWeight >> numItems;
vector<vector<pair<int, int>>> bins(maxWeight + 1);
for(int i = 0; i < numItems; i++) {
int value, weight, copies;
cin >> value >> weight >> copies;
if(weight <= maxWeight) {
bins[weight].push_back(make_pair(value, min(maxWeight / weight, copies)));
}
}
vector<int> dp(maxWeight + 1);
for(int weight = 1; weight <= maxWeight; weight++) {
vector<pair<int, int>> currentBin = bins[weight];
sort(currentBin.begin(), currentBin.end(), greater<pair<int, int>>());
// iterate over all indices in dp that can be changed
for(int i = maxWeight; i - weight >= 0; i--) {
int maxValue = dp[i];
int sum = 0;
int itemIndex = -1;
int itemCount = 0;
for(int j = i - weight; j >= 0; j -= weight) {
if(itemCount == 0) {
itemIndex++;
if(itemIndex == currentBin.size()) {
// ran out of items
break;
}
itemCount = currentBin[itemIndex].second;
}
sum += currentBin[itemIndex].first;
itemCount--;
maxValue = max(maxValue, sum + dp[j]);
}
dp[i] = maxValue;
}
}
cout << dp[maxWeight];
}
