#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n = 1e5 + 5;
vector<ll> v(n), w(n), k(n), user(2005, 0), hai(n), dp(n, 0);
bool cmd(ll a, ll b)
{
return v[a] > v[b];
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
ll s, n;
cin >> s >> n;
for (int i = 0; i < n; ++i) cin >> v[i] >> w[i] >> k[i];
iota(hai.begin(), hai.end(), 0);
sort(hai.begin(), hai.end(), cmd);
for (ll i : hai)
for (int efowefw = 0; efowefw < k[i]; ++efowefw)
{
if (user[w[i]] * w[i] > s) break;
for (int j = s; j >= w[i]; --j)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
user[w[i]] ++;
}
cout << dp[s];
}
