#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<
int,
null_type,
less_equal<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define ll long long int
#define fo(i, n) for (ll i = 0; i < n; i++)
#define Fo(i, k, n) for (ll i = k; i < n; i++)
#define fvr(it, v) for (auto it = v.rbegin(); it != v.rend(); ++it)
#define ALL(c) (c).begin(), (c).end() // handy for function like "sort()"
#define mod 1000000007
#define ff first
#define ss second
const long long MOD = 998244353;
const long long INF = 1e9 + 7;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vli;
typedef pair<int, int> pii;
long long sq(int x) { return 1ll * x * x; }
const int MAXN = 20000001;
// Sieve
// ll d[MAXN], divCnt[MAXN];
// vector<ll> primes;
// void sieve(ll n)
// {
// fo(i, n)
// {
// d[i] = i;
// }
// Fo(i, 2, n)
// {
// if (d[i] == i)
// primes.push_back(i);
// for (ll j = 0; j < ((ll)primes.size()) && primes[j] <= d[i] && primes[j] * i < n; j++)
// {
// d[i * primes[j]] = primes[j];
// }
// }
// Fo(i, 2, n)
// {
// ll j = i / d[i];
// divCnt[n] = divCnt[j] + (d[i] != d[j]);
// }
// }
// ll primeFactors(ll n)
// {
// set<ll> factors;
// while (n != 1)
// {
// factors.insert(d[n]);
// n /= d[n];
// }
// return factors.size();
// }
ll mul(ll x, ll y)
{
return (x * 1ll * y) % MOD;
}
ll binpow(ll a, ll b, ll c)
{
ll res = 1;
a = a % c;
while (b > 0)
{
if (b & 1)
res = (res * a) % c;
b = b >> 1;
a = (a * a) % c;
}
return res;
}
long long gcd(long long int a, long long int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// int fact[200043];
// void precalc()
// {
// fact[0] = 1;
// for (int i = 1; i < 200043; i++)
// fact[i] = mul(fact[i - 1], i);
// }
// Function to return LCM of two numbers
// int lcm(int a, int b)
// {
// return (a / gcd(a, b)) * b;
// }
ll inv(ll x, ll c)
{
return binpow(x, c - 2, c);
}
// int divide(int x, int y, int c)
// {
// return mul(x, inv(y, c));
// }
// int nCr(int n, int r, int c)
// {
// return divide(fact[n], mul(fact[r], fact[n - r]), c);
// }
bool cmp1(const pair<ll, ll> &a, const pair<ll, ll> &b)
{
if (a.first == b.first)
{
return a.second > b.second;
}
return a.first > b.first;
}
bool cmp2(const pair<ll, ll> &a, const pair<ll, ll> &b)
{
if (a.second == b.second)
{
return a.first < b.first;
}
return a.second > b.second;
}
ll find_sum(ll idx, vector<ll> &bit)
{
ll ans = 0;
for (; idx > 0; idx -= idx & (-idx))
ans += bit[idx];
return ans;
}
void update(ll pos, ll val, vector<ll> &bit)
{
for (; pos <= bit.size(); pos += pos & (-pos))
{
bit[pos] += val;
}
}
void solve()
{
ll S,n;
cin>>S>>n;
map<ll,vector<pair<ll,ll>>> weight;
fo(i,n){
ll v,w,k;
cin>>v>>w>>k;
weight[w].push_back({v,k});
}
ll cur=1;
ll dp[weight.size()+1][S+1];
fo(i,weight.size()+1){
fo(j,S+1)dp[i][j]=-LONG_LONG_MAX;
}
dp[0][0]=0;
ll ans=0;
for(auto& x:weight){
ll w=x.first;
auto k=x.second;
sort(ALL(k),cmp1);
fo(i,S+1){
dp[cur][i]=dp[cur-1][i];
ll amount=0, a=0,p=0,used=0;
while((amount+1)*w<=i && a<k.size()){
amount++;
p+=k[a].first;
if(dp[cur-1][i-amount*w]!=-LONG_LONG_MAX){
// cout<<dp[cur][i]<<" "<<i<<" "<<amount<<" "<<w<<" "<<cur<<endl;
dp[cur][i]=max(dp[cur][i],dp[cur-1][i-amount*w]+p);
ans=max(ans,dp[cur][i]);
}
used++;
if(used==k[a].second){
used=0;
a+=1;
}
}
}
cur+=1;
}
cout<<ans<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t, i = 0;
t = 1;
// freopen("feast.in", "r", stdin);
// freopen("feast.out", "w", stdout);
// cin >> t;
while (t--)
{
i++;
// cout<<"Case #"<<i<<": ";
solve();
}
}
