#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int s, n, v, w, k;
vector<pair<int, int>> items;
int main()
{
cin >> s >> n;
// pair<int, pair<int, int>> p[n + 1];
for (int i = 1; i <= n; i++)
{
// cin >> p[i].first >> p[i].second.first >> p[i].second.second;
cin >> v >> w >> k;
for (int j = 1; j <= min(k, (s + w - 1) / w); j++)
{
items.push_back({v, w});
}
}
n = items.size();
int dp[n + 1][s + 1];
for (int i = 0; i <= s; i++)
dp[0][i] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= s; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= items[i - 1].second)
{
dp[i][j] = max(dp[i][j], dp[i - 1][j - items[i - 1].second] + items[i - 1].first);
}
// cout << ":: " << i << ' ' << j << ' ' << dp[i][j] << '\n';
}
}
cout << dp[n][s] << '\n';
}
