#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, int> pill;
typedef vector<pill> vpill;
typedef vector<vpill> vvpill;
const ll inf = 1e18;
void update(int i, vll &T, int n, ll val)
{
//cout << i << ", " << i + n-1 << ", " << T.size() << ";\n";
i += n-1;
T[i] = val;
i/=2;
for(; i > 0; i/=2)
{
T[i] = max(T[i*2], T[i*2+1]);
}
}
int query(int l, int r, vll &T, int n)
{
//cout << l << ", " << l + n-1 << ", " << T.size() << "; ";
//cout << r << ", " << r + n-1 << ", " << T.size() << ";\n";
l += n-1;
r+= n-1;
ll ans = 0;
for(; l <= r; l >>= 1, r >>= 1)
{
if(l&1)
{
ans = max(T[l], ans);
l++;
}
if(!(r&1))
{
ans = max(T[r], ans);
r--;
}
}
//cout << ans << " ans \n";
return ans;
}
int main()
{
//freopen("..\\io\\input.txt", "r", stdin);
//freopen("..\\io\\output.txt", "w", stdout);
ios_base::sync_with_stdio(false);cin.tie(NULL);
int s, n; cin >> s >> n;
vll k(n+1, 0);
vll v(n+1, 0);
vll w(n+1, 0);
vvll dp(n+1, vll(s+1, 0));
for(int i = 1; i <= n; i++)
{
cin >> v[i] >> w[i] >> k[i];
}
for(int i = 1; i <= n; i++)
{
for(int m = 0; m <= max(s - w[i]*k[i], w[i]); m++)
{
vll vals;
for(int l = 0; l <= k[i] && m + l*w[i] <= s; l++)
{
vals.push_back(dp[i-1][m + l*w[i]] - v[i]*l);
}
int N = vals.size();
int n1 = 1 << (32 - (__builtin_clz(N-1)));
vll T(n1*2, 0);
for(int p = 0; p < N; p++)
{
update(p+1, T, n1, vals[p]);
}
for(int l = 0; l <= k[i] && m + l*w[i] <= s; l++)
{
dp[i][m+w[i]*l] = max(query(1, l+1, T, n1) + v[i]*l, dp[i][m+w[i]*l]);
/*f(i == 2)
{
cout << m << ", " << l << "; " << dp[i][m+w[i]*l] << ", " << m+w[i]*l << "\n";
}*/
}
}
}
ll ans = 0;
for(int i = 0; i <= s; i++)
{
ans = max(ans, dp[n][i]);
}
/*for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= s; j++)
{
cout << dp[i][j] << " ";
}
cout << "\n";
}*/
cout << ans << "\n";
}
