#define taskname "Knapsack"
#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
using namespace std;
const int maxn = 2010;
vector<ii> a[maxn], b[maxn];
int dp[maxn], n, S, val[10*maxn], wt[10*maxn];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin>>S>>n;
for (int i=1; i<=n; i++)
{
int v, w, k;
cin>>v>>w>>k;
a[w].emplace_back(v, k);
}
int dem = 1;
for (int i=1; i<=2000; i++)
{
sort(a[i].begin(), a[i].end());
int cur = 0, up = S/i;
for (auto [v, k]: a[i])
{
if (cur >= up) break;
if (cur+k <= up) b[i].emplace_back(v, k), cur += k;
else
{
b[i].emplace_back(v, up-cur);
break;
}
}
for (auto [v, c]: b[i])
{
for (int j=dem; j<=dem+c-1; j++) val[j] = v, wt[j] = i;
dem += c;
}
}
dem--;
//cout<<dem<<"\n";
//for (int i=1; i<=dem; i++) cout<<val[i]<<" "<<wt[i]<<"\n";
for (int i=1; i<=dem; i++)
for (int weight=S; weight>=wt[i]; weight--)
if (dp[weight-wt[i]] || weight==wt[i])
dp[weight] = max(dp[weight], dp[weight-wt[i]]+val[i]);
cout<<*max_element(dp+1, dp+S+1);
}
