#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, n;
cin >> S >> n;
map<int, vector<pair<int, int>>> wgr;
for(int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
if(w <= S) {
wgr[w].push_back({v, k});
}
}
vector<pair<int, int>> f;
for(auto [w, items] : wgr) {
vector<pair<int, int>> sorted = items;
sort(sorted.rbegin(), sorted.rend());
int tot = S / w;
int curr = 0;
for(auto &[v, k] : sorted) {
int take = min(k, tot - curr);
curr += take;
for(int i = 1; take; i <<= 1) {
int num = min(i, take);
f.push_back({num * v, num * w});
take -= num;
}
}
}
vector<ll> dp(S + 1);
for(auto item : f) {
for(int j = S; j >= item.second; --j) {
dp[j] = max(dp[j], dp[j - item.second] + item.first);
}
}
cout << ranges::max(dp);
return 0;
}
