#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define vi vector<int>
#define vs vector<string>
#define vb vector<bool>
#define vpi vector<pi>
#define pb push_back
#define all(a) (a).begin(), (a).end()
const int mod = 1e9 + 7;
int s, n;
int MAXS = 2002;
void solve()
{
int v, w, k;
cin >> v >> w >> k;
int b = min(s / w, k);
cout << b * v << '\n';
}
bool cmp(pi a, pi b)
{
return a.first > b.first;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> s >> n;
if (n == 1)
{
solve();
return 0;
}
vi val;
vi wts;
vector<vpi> wg(MAXS);
for (int i = 0; i < n; i++)
{
int v, w, k;
cin >> v >> w >> k;
wg[w].pb({v, k});
}
for (int i = 1; i < MAXS; i++)
{
sort(all(wg[i]), cmp);
int j = s / i;
int x = 0;
while (x < wg[i].size() && max(j, wg[i][x].second) > 0)
{
if (j == 0)
break;
if (wg[i][x].second == 0)
{
x++;
continue;
}
j--;
wg[i][x].second--;
val.pb(wg[i][x].first);
wts.pb(i);
}
}
vector<vi> dp(2, vi(s + 1, 0));
for (int i = 1; i <= val.size(); i++)
{
for (int j = 0; j <= s; j++)
{
dp[1][j] = dp[0][j];
if (j >= wts[i - 1])
{
dp[1][j] = max(dp[1][j], dp[0][j - wts[i - 1]] + val[i - 1]);
}
}
dp[0] = dp[1];
}
cout << dp[1][s] << '\n';
}
