#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = -2e9;
const int MAXS = 2100;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
vector<vector<pair<int,int>>> items(S + 1); // items[w] = list of {value, count}
// Input all items grouped by weight
for (int i = 0; i < N; ++i) {
int v, w, k;
cin >> v >> w >> k;
k = min(k, S / w); // no need for more than S/w items of this type
items[w].push_back({v, k});
}
// Sort each group by value descending (to take higher-value items first)
for (int w = 1; w <= S; ++w)
sort(items[w].rbegin(), items[w].rend());
// Flatten items into single list of (weight, value)
vector<pair<int,int>> all;
for (int w = 1; w <= S; ++w) {
int capacity = S / w; // max items of weight w we could take
for (auto &[v, k] : items[w]) {
int take = min(k, capacity);
for (int t = 0; t < take; ++t)
all.push_back({w, v});
capacity -= take;
if (capacity == 0) break;
}
}
// Standard 0/1 knapsack on the flattened list
vector<int> dp(S + 1, INF);
dp[0] = 0;
for (auto &[w, v] : all)
for (int s = S; s >= w; --s)
dp[s] = max(dp[s], dp[s - w] + v);
cout << *max_element(dp.begin(), dp.end()) << '\n';
}
