#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 = 0; j<limit; ++j)
{
m[wt[i]].push_back(val[i]);
}
}
/*
for(auto& [w, vals]:m)
{
cout << w << endl;
for(int v : vals)
{
cout << v << " ";
}
cout << endl;
}
cout << endl;
*/
vector<pair<int, int>>final_items;
for(auto& [w, vals]: m)
{
int cnt = S/w;
int sz = vals.size();
// cout << "cnt: " << cnt << " sz: " << sz << endl;
if(sz>cnt)
{
sort(vals.begin(), vals.end(), greater<>());
vals.resize(cnt);
}
for(int it : vals)
{
final_items.push_back({w,it});
}
}
/*
for(auto& [i, j]: final_items)
{
cout << i << " " << j << endl;
}
*/
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;
}
