#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
int main()
{
int S, N;
cin >> S >> N;
vpll occ[1+S];
for(int i = 1; i <= N; i++)
{
int v, w, k;
cin >> v >> w >> k;
occ[w].push_back({v, k});
}
vpll items; //value, weight
for(int w = 1; w <= S; w++)
{
int lim = S/w;
sort(occ[w].begin(), occ[w].end());
while(!occ[w].empty() && lim > 0)
{
if(occ[w].back().second == 0)
{
occ[w].pop_back();
continue;
}
else
{
occ[w].back().second--;
items.push_back({occ[w].back().first, w});
lim--;
}
}
}
vll dp(1+S, 0);
for(pll I : items)
{
for(ll w = S; w >= I.second; w--)
dp[w] = max(dp[w], dp[w - I.second] + I.first);
}
cout << dp[S] << '\n';
}
