#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vpi vector<pair<int,int>>
using namespace std;
int main()
{
int s, n;
cin >> s >> n;
vector<vpi> item(s+1);
for (int i = 0; i < n; i++)
{
int v, w, k;
cin >> v >> w >> k;
item[w].push_back({v, k});
}
for (int i = 0; i <= s; i++)
{
sort(item[i].begin(), item[i].end(), greater<pair<int, int>>());
}
vpi collection;
for (int i = 1; i <= s; i++)
{
// for ith weight make sum upto s
int w = 0;
for (auto &&p : item[i])
{
int v = p.first;
int k = p.second;
while (k--)
{
if(w+i <= s)
{
w += i;
collection.push_back({i, v});
}
else
break;
}
if(w+i > s)
break;
}
}
int m = collection.size();
int dp[m][s+1];
memset(dp, 0, sizeof dp);
dp[0][collection[0].first] = collection[0].second;
for (int i = 1; i < m; i++)
{
for (int w = 1; w <= s; w++)
{
dp[i][w] = dp[i-1][w];
int x = collection[i].first;
int v = collection[i].second;
if(w >= x)
dp[i][w] = max(dp[i][w], dp[i-1][w-x]+v);
}
}
int ans = 0;
for (int w = 0; w <= s; w++)
{
ans = max(dp[m-1][w], ans);
}
cout << ans << endl;
}
