#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;
#define v vector
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define F first
#define S second
#define ll long long
#define pll pair<long long, long long>
#define sz(p) p.size()
#define all(x) x.begin(), x.end()
int n, s;
v<ll> va(100005), dp1(2001);
v<v<ll>> dp(104, v<ll>(2001));
v<int> w(100005), k(100005);
v<bool> touched(2001, 0);
v<v<bool>> in(2, v<bool>(2001));
int main()
{
cin >> s >> n;
ll ans = 0;
for (int i = 0; i < n; i++)
cin >> va[i] >> w[i] >> k[i];
for (int i = 1; i <= k[0] && i * w[0] <= s; i++)
dp[0][i * w[0]] = i * va[0];
in[1][0] = 1;
for (int i = 1; i <= k[0] && i * w[0] <= s; i++)
{
dp1[i * w[0]] = i * va[0];
in[1][i * w[0]] = 1;
}
in[0] = in[1];
// cout << dp[0][w[0]] << endl;
// cout << "max_index: 0" << endl;
// for (int k = 0; k <= s; k++)
// cout << dp[0][k] << ' ';
// cout << endl;
/*for (int i = s; i >= 0; i--)
{
for (int j = 0; j < n; j++)
{
for (int q = 0; q <= k[j]; q++)
{
if (q * w[j] > i)
break;
if (dp1[i - (q * w[j])] || i == q * w[j])
dp1[i] = max(dp1[i], dp1[i - (q * w[j])] + (ll)q * va[j]);
// if (dp[j - 1][i - (q * w[j])] || i == q * w[j])
// dp[j][i] = max(max(dp[j][i], dp[j - 1][i - (q * w[j])] + (ll)q * va[j]), dp[j - 1][i]);
cout << i << ' ' << q << endl;
cout << i << ' ' << dp[j][i] << ' ' << dp[j][i - 1] << endl;
}
for (int k = 0; k <= s; k++)
cout << dp1[k] << ' ';
cout << endl;
}
}*/
for (int j = 1; j < n; j++)
{
// cout << "max_index: " << j << endl;
for (int i = 0; i <= s; i++)
{
if (!in[0][i])
continue;
if (touched[i])
continue;
// dp[i] = max(dp[i - (q * w[j])] + q * va[j], dp[i]);
for (int q = 1; q <= k[j]; q++)
{
int add = q * w[j];
// if (touched[i + add])
// continue;
if (i + add > s)
continue;
ll prev = dp1[i + add];
dp1[i + add] = max(dp1[i + add], dp1[i] + (ll)q * va[j]);
in[1][i + add] = 1;
if (dp1[i + add] > prev)
touched[i + add] = 1;
// if (dp[j - 1][i - (q * w[j])] || i == q * w[j])
// dp[j][i] = max(max(dp[j][i], dp[j - 1][i - (q * w[j])] + (ll)q * va[j]), dp[j - 1][i]);
// cout << i << ' ' << q << endl;
// cout << i << ' ' << dp[j][i] << ' ' << dp[j][i - 1] << endl;
}
// cout << "weight: " << i << endl;
// for (int k = 0; k <= s; k++)
// cout << dp1[k] << ' ';
// cout << endl;
}
in[0] = in[1];
touched.assign(2001, 0);
}
for (int i = 0; i <= s; i++)
ans = max(ans, dp1[i]);
cout << ans << endl;
}
