#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N int(1e5 + 5)
#define M int(2e3 + 5)
#define MOD int(1e9 + 7)
#define base 311
int n, m, ans;
int w[N], v[N], a[N], in[N];
int d[M];
typedef pair <int, int> ii;
vector < vector <ii> > f(M);
bool cmp(int i, int j)
{
return w[i] < w[j];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("KNAPSACK.inp","r",stdin);
// freopen("KNAPSACK.out","w",stdout);
for (int i = 0; i <= M-5; i++) f[i].push_back(ii(-1, 0));
f[0][0].first = 0;
cin >> m >> n;
for (int i = 1; i <= n; i++)
{
cin >> v[i] >> w[i] >> a[i];
if (!w[i]) f[0].back().first += v[i] * a[i];
in[i] = i;
}
sort(in+1, in+1+n, cmp);
for (int i = 1; i <= n; i++)
{
if (!w[in[i]]) continue;
for (int j = 0; j <= m; j++)
{
int tmp = 0;
while (f[j].size())
{
if (f[j].back().first != -1 && j + w[in[i]] <= m && f[j].back().second < a[in[i]] && f[j+w[in[i]]][0].first < f[j].back().first + v[in[i]])
f[j+w[in[i]]].push_back(ii(f[j].back().first + v[in[i]], f[j].back().second + 1));
tmp = max(tmp, f[j].back().first);
f[j].pop_back();
}
f[j].push_back(ii(tmp, 0));
}
}
for (int i = 0; i <= m; i++) ans = max(ans, f[i].back().first);
cout << ans;
cout << '\n';
return 0;
}
