#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1E9 + 7, MX = 1E6 + 2;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// int T;
// cin >> T;
// for (int t = 1; t <= T; t++)
// {
int S, N;
cin >> S >> N;
vector<int> V(N);
vector<int> R(N);
vector<int> K(N);
vector<vector<int>> group_by_gas_req(S + 1);
for (int i = 0; i < N; i++)
{
cin >> R[i] >> V[i] >> K[i];
group_by_gas_req[V[i]].push_back(i);
}
vector<vector<ll>> dp(S + 1, vector<ll>(S + 1, 0));
auto compare = [&R](int a, int b)
{
return R[a] > R[b];
};
for (int i = 1; i <= S; i++)
{
sort(group_by_gas_req[i].begin(), group_by_gas_req[i].end(), compare);
// reverse(group_by_gas_req[i].begin(), group_by_gas_req[i].end());
// for (int x : (group_by_gas_req[i]))
// {
// cout << R[x] << " ";
// }
// cout << "\n";
for (int j = 1; j <= S; j++)
{
ll k_maximum = S / i, val = 0, cumulative_k = 1;
int k = 1, l = 0;
while (k_maximum > 0 && l < group_by_gas_req[i].size())
{
val += (R[group_by_gas_req[i][l]]);
// cout << i << " " << j << " " << max(dp[i - 1][j - min(j, k * i)] + (((k * i) <= j) ? val : 0), dp[i - 1][j]) << "\n";
dp[i][j] = max(max(dp[i - 1][j - min((ll)j, cumulative_k * i)] + (((cumulative_k * i) <= j) ? val : 0), dp[i - 1][j]), dp[i][j]);
k++;
cumulative_k++;
k_maximum--;
if (k > K[group_by_gas_req[i][l]])
{
k = 1;
l++;
}
}
dp[i][j] = max(dp[i - 1][j], dp[i][j]);
}
}
// for (int i = 1; i < S; i++)
// {
// for (int j = 1; j < S; j++)
// {
// cout << dp[i][j] << " ";
// }
// cout << "\n";
// // }
// }
cout << dp[S][S] << "\n";
}
