#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct item{int val, cnt;};
vector<item> A[2002];
int dp[101][101];
// dp[i][j] - considerand greutati pana la i care e
// valoarea maxima obtinuta cu capacitatea j.
bool cmp(item a, item b)
{
return a.val > b.val;
}
int main()
{
int S, N;
cin >> S >> N;
for(int i = 1;i<=N;i++)
{
int v, w, k;
cin >> v >> w >> k;
A[w].push_back({v,k});
}
for(int i = 1;i<=S;i++)
if(!A[i].empty())
sort(A[i].begin(),A[i].end(),cmp);
for(int i = 1;i<=S;i++) // consideram greutatea i
{
// Avem un rucsac cu capacitatea G
for(int G = 1;G<=S;G++)
{
int sumV = 0, taken = 0 ;
dp[i][G] = dp[i-1][G];
for(int j = 0; j < A[i].size();j++)
{
// Ne aflam intr-un item si nu stim cate sa luam din el.
if(taken + 1 > G / i) break;
for(int it = 1; it <= A[i][j].cnt;it++)
{
if(taken + 1 > G / i) break;
taken++;
sumV += A[i][j].val;
dp[i][G] = max(dp[i][G], dp[i - 1][G - taken * i] + sumV);
}
}
}
}
cout << dp[S][S] << '\n';
}
