///TRAN THAI BAO :3
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define maxS 2007
#define maxN 30007
typedef pair<long long, long long> pii;
int n;
long long S;
vector<pii>itm[maxS];
vector<pii>realItm;
long long dp[maxN][maxS] = {0};
bool cmp(pii x, pii y)
{
return x.first > y.first;
}
void readData()
{
realItm.push_back({0, 0});
cin >> S >> n;
long long v, w, a;
for(int i = 1; i <= n; i++)
{
cin >> v >> w >> a;
itm[w].push_back({v, a});
}
for(int i = 1; i <= S; i++)
{
sort(itm[i].begin(), itm[i].end(), cmp);
int lim = S/i, cnt = 0;
for(int j = 0; j < itm[i].size(); j++)
{
if(cnt >= lim)break;
for(int k = 0; k < itm[i][j].second; k++)
{
realItm.push_back({itm[i][j].first, i});
cnt++;
if(cnt >= lim)break;
}
}
}
n = realItm.size()-1;
}
void knapSack()
{
for(int i = 1; i <= n; i++)
{
pii cur = realItm[i];
for(int j = 0; j <= S; j++)
{
dp[i][j] = max(dp[i][j], dp[i-1][j]);
if(cur.second <= j)
dp[i][j] = max(dp[i][j], dp[i-1][j-cur.second]+cur.first);
}
}
cout << dp[n][S];
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
readData();
knapSack();
return 0;
}
