#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
#define vi vector<int>
#define all(x) (x).begin(), (x).end()
#define input(v, n) \
for (int i = 0; i < n; i++) \
cin >> v[i];
void compute()
{
int s, n;
cin >> s >> n;
vector<pair<int, pair<int, int>>> arr(n);
for (int i = 0; i < n; i++)
{
int v, w, k;
cin >> v >> w >> k;
arr[i].first = w;
arr[i].second.first = v;
arr[i].second.second = k;
}
sort(arr.begin(), arr.end(), [](const pair<int, pair<int, int>> &a, const pair<int, pair<int, int>> &b)
{
if(a.first > b.first)return true;
else if(a.first == b.first)return a.second.first > b.second.first;
return false; });
vector<int> weights, value;
int tw = s;
int cur = arr[0].first;
int curcnt = 0;
for (int i = 0; i < arr.size(); i++)
{
if (arr[i].first != cur)
{
cur = arr[i].first;
curcnt = 0;
}
int last = min(arr[i].second.second, (tw / cur) - curcnt);
curcnt += last;
for (int j = 0; j < last; j++)
{
weights.push_back(cur);
value.push_back(arr[i].second.first);
}
}
vector<vector<int>> dp(weights.size() + 1, vector<int>(s + 1, 0));
for (int i = 0; i < weights.size() + 1; i++)
{
dp[i][0] = 0;
}
for (int i = 1; i < weights.size() + 1; i++)
{
for (int j = 1; j < s + 1; j++)
{
if (weights[i - 1] <= j)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + value[i - 1]);
else
dp[i][j] = dp[i - 1][j];
}
}
cout << dp[weights.size()][s];
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
while (t--)
compute();
return 0;
}
