#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAX = (2e3) + 5, MAX2 = (1e5) + 5;
long long n, s, dp[MAX];
vector<long long> w[MAX];
struct Cell
{
long long v, w, k;
} a[MAX2];
bool Cmp(Cell a, Cell b)
{
if (a.w == b.w)
return a.v > b.v;
return a.w < b.w;
}
void Solve()
{
cin >> s >> n;
for (long long i = 1; i <= n; i++)
{
cin >> a[i].v >> a[i].w >> a[i].k;
}
sort(a + 1, a + n + 1, Cmp);
for (long long i = 1; i <= n; i++)
{
for (long long j = 1; j <= a[i].k; j++)
{
if (w[a[i].w].size() >= s / a[i].w)
break;
w[a[i].w].push_back(a[i].v);
}
}
for (long long i = 1; i <= s; i++)
{
for (auto val : w[i])
{
for (long long j = s; j >= i; j--)
dp[j] = max(dp[j], dp[j - i] + val);
}
}
long long ans = 0;
for (long long i = 1; i <= s; i++)
ans = max(ans, dp[i]);
cout << ans << endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
Solve();
return 0;
}
