#include <bits/stdc++.h>
using namespace std;
#define tup tuple<int, int, int>
const int nx = 2e3+5;
int s, n, dp[nx];
vector<tup> a;
vector<pair<int, int>> q;
bool cmp(tup& x, tup& y)
{
auto [x1, x2, x3] = x;
auto [y1, y2, y3] = y;
if(x1 == y1) return x2 > y2;
return x1 < y1;
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin >> s >> n;
for(int i=0;i<n;i++)
{
int v, w, k;
cin >> v >> w >> k;
a.push_back({w, v, k});
}
sort(a.begin(), a.end(), cmp);
int cnt = 0, prev = -1;
for(auto& [w, v, k] : a)
{
if(prev != w)
{
cnt = 0;
prev = w;
}
int weight = s / w;
for(int j=0;j<k && cnt<weight;j++) q.push_back({v, w}), cnt++;
}
for(auto& [v, w] : q)
{
for(int i=s;i>=0;i--)
{
if(i - w < 0) continue;
dp[i] = max(dp[i], dp[i - w] + v);
}
}
cout << dp[s];
return 0;
}
