#include <bits/stdc++.h>
using namespace std;
struct Item {long long V,W,K;};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S,N;
cin >> S >> N;
vector<Item> items(N);
for (auto &it : items) cin >> it.V >> it.W >> it.K;
// Bỏ vật vô dụng
vector<Item> useful;
useful.reserve(N);
for (auto &it: items)
if (it.V>0 && it.W>0 && it.W<=S && it.K>0)
useful.push_back(it);
swap(items,useful);
// Gộp vật trùng (W,V)
sort(items.begin(), items.end(), [](auto &a, auto &b){
if (a.W!=b.W) return a.W<b.W;
return a.V<b.V;
});
vector<Item> merged;
for (auto &it: items) {
if (!merged.empty() && merged.back().W==it.W && merged.back().V==it.V)
merged.back().K += it.K;
else merged.push_back(it);
}
swap(items, merged);
vector<long long> dp(S+1,0);
for (auto &it: items) {
long long V=it.V, W=it.W, K=it.K;
if (K*W>=S) {
for (int s=W; s<=S; ++s)
if (dp[s-W]+V>dp[s]) dp[s]=dp[s-W]+V;
} else {
long long remain=K, t=1;
while (remain>0) {
long long num=min(t,remain);
int wt=int(num*W);
long long val=num*V;
for (int s=S; s>=wt; --s)
if (dp[s-wt]+val>dp[s]) dp[s]=dp[s-wt]+val;
remain-=num; t<<=1;
}
}
}
cout << *max_element(dp.begin(), dp.end()) << "\n";
}
