#include <bits/stdc++.h>
using namespace std;
#define ioss \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0)
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
int t, n;
int l[100004], e[100004], k[100004];
signed main()
{
ioss;
cin >> t >> n;
for (int i = 1; i <= n; i++){
cin >> l[i] >> e[i] >> k[i];
}
int dp[n + 1][t + 1];
for(int i = 0; i <= n; i++){
for(int j = 0; j <= t; j++){
dp[i][j] = 0;
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= t; j++)
{
dp[i][j] = dp[i - 1][j];
// cout << dp[i][j] << ' ';
for (int x = 1; x <= k[i]; x++)
{
if (x * e[i] > j)
break;
dp[i][j] = max(dp[i - 1][j - (x * e[i])] + (x * l[i]), dp[i][j]);
}
// cout << dp[i][j] << ' ';
}
cout << '\n';
}
cout << dp[n][t] << endl;
}
