#include <bits/stdc++.h>
using namespace std;
bool rikiavimas(pair<int, int> a, pair<int, int> b)
{
return a.first > b.first;
}
int main()
{
int S, N;
cin >> S >> N;
vector<pair<int, int>> Duom[2001];
for(int i = 0; i<N; i++)
{
int kaina, svoris, kiekis;
cin >> kaina >> svoris >> kiekis;
Duom[svoris].push_back({kaina, kiekis});
}
//cout << '!' << endl;
vector<int> Pasirinkimai[2001];
for(int i = 1; i<=2000; i++)
{
//cout << '!';
if(Duom[i].size() > 0) sort(Duom[i].begin(), Duom[i].end(), rikiavimas);
int riba = 2000/i+1; ///atkreipti demesi ateity
int kur = 0;
int kiek = 0;
//cout << '?' << endl;;
for(int j = 0; j<riba; j++)
{
//if(i == 3)cout << j << endl;
if(kur > int(Duom[i].size())-1)
{
Pasirinkimai[i].push_back(-1);
continue;
}
//cout << '.' << endl;
if(kiek > Duom[i][kur].second-1)
{
kur++;
kiek = 0;
}
if(kur > Duom[i].size()-1)
{
Pasirinkimai[i].push_back(-1);
continue;
}
Pasirinkimai[i].push_back(Duom[i][kur].first);
kiek++;
}
//cout << endl;
}
//ofstream cout ("isvestis.txt");
/*for(int i = 0; i<=2000; i++)
{
for(int j = 0; j<Pasirinkimai[i].size(); j++)
{
cout << Pasirinkimai[i][j] << ' ';
}
cout << endl;
}*/
vector<int> tuscias(2001, -1);
deque<vector<int>> dp;
dp.push_back(tuscias);
dp[0][0] = 0;
for(int i = 1; i<=2000; i++)
{
dp.push_back(dp[0]);
for(int j = 0; j<=2000; j++)
{
if(dp[0][j] == -1) continue;
int suma = 0;
int sk=0;
for(int k = j+i; k<=2000; k+=i)
{
if(Pasirinkimai[i][sk] == -1) break;
suma += Pasirinkimai[i][sk++];
dp[1][k] = max(dp[1][k], dp[0][j] + suma);
}
}
/*for(int j = 0; j<=S; j++)
{
cout << dp[1][j] << ' ';
}
cout << endl;*/
dp.pop_front();
}
int ats = -1;
for(int i = 0; i<=S; i++) ats = max(ats, dp[0][i]);
cout << ats;
return 0;
}
/*
10 5
4 1 3
3 1 8
9 2 17
7 5 7
15 6 5
*/
