#include<bits/stdc++.h>
using namespace std;
#define int long long
bool cmp(pair<int,int> &a , pair<int,int> &b)
{
if(a.first == b.first)
return a.second > b.second;
return a.first > b.first;
}
int32_t main()
{
ios :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int s , n ; cin >> s >> n;
vector<pair<int,int>> best[s+1];
for(int i = 0 ; i < n ; i++)
{
int val , wt , q; cin >> val >> wt >> q;
best[wt].push_back({val,q});
}
vector<int> dp(s + 1);
vector<int> wt , val;
for(int i = 1 ; i <= s ; i++)
{
sort(best[i].begin(),best[i].end(),cmp);
int q = 0;
for(auto x : best[i])
{
int y = 1;
while(1)
{
if(q > s) break;
if(x.second == 0) break;
if(y >= x.second)
y = x.second;
wt.push_back(i * y);
q += i * y;
val.push_back(x.first * y);
x.second -= y;
y *= 2;
}
if(q > s) break;
}
}
for(int j = 0 ; j < val.size() ; j++)
{
for(int i = s ; i >= 0 ; i--)
{
if(i >= wt[j])
dp[i] = max(dp[i] , dp[i - wt[j]] + val[j]);
}
}
cout << *max_element(dp.begin(),dp.end());
}
