#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
#define F0R(i, a, b) for (int i = (a); i < (b); i++)
#define FOR(i, a) F0R(i, 0, a)
#define f first
#define s second
ll cx[] = {0, 1, 0, -1};
ll cy[] = {1, 0, -1, 0};
const ll INF = 1e9 + 7;
struct item
{
int p;
int w;
int amount;
};
// auto start = chrono::steady_clock::now();
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t, n;
cin >> t >> n;
vector<item> v(n+1);
for (int i = 1; i <= n; i++) cin >> v[i].p >> v[i].w >> v[i].amount;
vector<int> dp(t+1, 0);
int ans = 0;
for (int i = 1; i <= n; i++)
{
int times = min(v[i].amount, (t / v[i].w) + 1);
for (int j = 0; j < times; j++)
{
for (int k = t; k >= 0; k--)
{
if (dp[k] > 0 && k + v[i].w <= t)
{
dp[k + v[i].w] = max(dp[k + v[i].w], dp[k] + v[i].p);
ans = max(ans, dp[k + v[i].w]);
}
else if (k == v[i].w)
{
dp[k] = max(dp[k], v[i].p);
ans = max(ans, dp[k]);
}
}
}
}
cout << ans;
// cout << "\n";
// auto end = chrono::steady_clock::now();
// auto diff = end - start;
// cout << chrono::duration<double, milli>(diff).count() << " ms" << endl;
return 0;
}
