#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
vector<vector<int>> bucket(S + 1);
for (int i = 0; i < N; i++) {
int v, w, k;
cin >> v >> w >> k;
int cnt = min(k, S / w);
for (int j = 0; j < cnt; j++) {
bucket[w].push_back(v);
}
}
vector<pair<int,int>> items;
for (int w = 1; w <= S; w++) {
auto &vec = bucket[w];
sort(vec.rbegin(), vec.rend());
int take = min((int)vec.size(), S / w);
for (int i = 0; i < take; i++) {
items.push_back({w, vec[i]});
}
}
vector<int> dp(S + 1);
for (auto [w, v] : items) {
for (int j = S; j >= w; j--) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
cout << *max_element(dp.begin(), dp.end());
return 0;
}
