#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Cake
{
int v, k;
};
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int s, n;
cin >> s >> n;
vector<vector<Cake>> a(s + 1);
for(int i = 0; i < n; i++)
{
int v, w, k;
cin >> v >> w >> k;
if(w <= s)
a[w].push_back({v, k});
}
vector<pair<int, int>> pick;
for(int w = 1; w <= s; w++)
{
if(a[w].empty()) continue;
sort(a[w].begin(), a[w].end(),
[](const Cake& x, const Cake& y)
{
return x.v > y.v;
});
int cap = s / w;
for(auto &ck : a[w])
{
int t = min(ck.k, cap);
if(t == 0) break;
cap -= t;
for(int b = 1; t > 0; b <<= 1)
{
int num = min(b, t);
pick.push_back({num * ck.v, (int)(num * w)});
t -= num;
}
if(cap == 0) break;
}
}
vector<int> dp(s + 1, 0);
for(auto &it : pick)
{
int val = it.first;
int wt = it.second;
for(int j = s; j >= wt; j--)
dp[j] = max(dp[j], dp[j - wt] + val);
}
cout << *max_element(dp.begin(), dp.end());
return 0;
}
