#include <bits/stdc++.h>
#define int long long
using namespace std;
int32_t main() {
int S, N;
cin >> S >> N;
vector<int>val(N);
vector<int>wt(N);
vector<int>k(N);
map<int, vector<int>>m;
for(int i = 0; i<N; ++i)
{
cin >> val[i] >> wt[i] >> k[i];
int limit = min(S/wt[i], k[i]);
for(int j = 1; limit>0; j<<=1)
{
int p = min(j, limit);
int weight = p*wt[i];
int value = p*val[i];
m[weight].push_back(value);
limit-=p;
}
}
vector<pair<int, int>>final_items;
for(auto& [w, vals]: m)
{
int cnt = S/w;
int sz = vals.size();
if(sz>cnt)
{
sort(vals.begin(), vals.end(), greater<>());
vals.resize(cnt);
}
for(int it : vals)
{
final_items.push_back({w,it});
}
}
vector<int>dp(S+1, 0);
for(auto& [it1, it2] : final_items)
{
for(int j = S; j>=it1; --j)
{
dp[j] = max(dp[j], dp[j-it1] + it2);
}
}
cout << dp[S];
return 0;
}
