#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int S, N;
cin >> S >> N;
map<int, vector<pair<int, int>>> by_weight;
for (int i = 0; i < N; ++i){
int v, w, k;
cin >> v >> w >> k;
by_weight[w].push_back({v, k});
}
vector<vector<long long>> best(by_weight.size() + 1, vector<long long>(S + 1, -1));
best[0][0] = 0;
int at = 1;
for (pair<int, vector<pair<int, int>>> p : by_weight){
int w = p.first;
vector<pair<int, int>> items = p.second;
sort(items.begin(), items.end(), greater<pair<int, int>>());
for (int i = 0; i <= S; ++i){
best[at][i] = best[at - 1][i];
int copies = 0, type_at = 0, curr_used = 0;
long long profit = 0;
while ((copies + 1) * w <= i && type_at < items.size()){
copies++;
profit += items[type_at].first;
if (best[at - 1][i - copies * w] != -1) best[at][i] = max(best[at][i], best[at - 1][i - copies * w] + profit);
curr_used++;
if (curr_used >= items[type_at].second){
curr_used = 0;
type_at++;
}
}
}
at++;
}
cout << *max_element(best.back().begin(), best.back().end());
return 0;
}
