#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;
const ll INF = 1e18 + 7;
void solve()
{
ll s, n;
cin >> s >> n;
vector<ll> v(n), w(n), k(n);
for (int i = 0; i < n; i++)
{
cin >> v[i] >> w[i] >> k[i];
}
if (n == 1)
{
cout << (s / w[0]) * v[0] << endl;
return;
}
vector<vector<ll>> dp(n, vector<ll>(s + 1));
// dp[i][j] = max value which she can get until ind i and remaining weight is j
// base case:- dp[0][j] = (j/w[0])*v[0] dp[i][0] = 0;
for (int j = 0; j <= s; j++)
{
if (j / w[0] <= k[0])
{
dp[0][j] = (j / w[0]) * v[0];
}
}
for (int i = 1; i < n; i++)
{
for (int j = 0; j <= s; j++)
{
dp[i][j] = dp[i - 1][j];
for (int x = 1; x <= k[i] && x * w[i] <= j; x++)
{
dp[i][j] = max(dp[i][j], dp[i - 1][j - x * w[i]] + x * v[i]);
}
}
}
cout << dp[n - 1][s] << endl;
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
t = 1;
while (t--)
{
solve();
}
return 0;
}
