#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long int
#define umap unordered_map
#define mod 998244353ll
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define MN(a,b,c) min(a,min(b,c))
#define MX(a,b,c) max(a,max(b,c))
#define pr1 pair<ll,ll>
#define F first
#define S second
#define mP make_pair
#define f(i,n) for(ll i=0;i<n;i++)
#define f1(i,x,y) for(ll i=x;i<=y;i++)
#define f2(i,x,y) for(ll i=x;i>=y;i--)
#define yes cout<<"Yes"<<"\n"
#define no cout<<"No"<<"\n"
#define modsum(a,b) ((a%mod)+(b%mod))%mod
#define modpro(a,b) ((a%mod)*(b%mod))%mod
#define moddif(a,b) ((a%mod)-(b%mod)+mod)%mod
#define modsumt(a,b,c) modsum(a,modsum(b,c))
// Remove macro of endl in interactive task
// in case of no errors check macros and functions again
//__builtin_popcount(x)
//__builtin_parity(x) =(number of set bits)%2
//__builtin_clz(x) to count the number of leading zeroes
//__builtin_ctz(x) to count the number of trailing zeroes
//__gcd(a,b)
// Binary Search
// TO AVOID GETTING INFINITE LOOP
// mid = (l+r)/2 l=mid+1 r=mid
// mid = (l+r+1)/2 l=mid r=mid-1
//std::cout << std::fixed; std::cout << std::setprecision(12); std::cout << z ;
using namespace std;
bool cmp(pair<ll,pair<ll,ll>> a,pair<ll,pair<ll,ll>> b)
{
if(a.F == b.F)
{
return a.S.F > b.S.F;
}
else return a.F<b.F;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll s,n;cin>>s>>n;
vector <pair<ll,pair<ll,ll>>> v(n);
f(i,n)
{
ll val,wei,freq;
cin>>val>>wei>>freq;
v[i]={wei,{val,freq}};
}
vector <ll> dp(s+1,-1);
dp[0]=0;
sort(all(v),cmp);
ll c=0;
f(i,n)
{
ll wei=v[i].F;
ll val=v[i].S.F;
ll freq=v[i].S.S;
ll lim = s/wei;
if(i>0 && v[i].F==v[i-1].F)
{
freq=min(freq,lim-c);
c+=freq;
}
else
{
c=freq;
freq=min(freq,lim);
}
if(freq>0)
{
for(ll j=s;j>=0;j--)
{
ll c=1,VAL=val,WEI=wei;
while(c<=freq && WEI<=j)
{
if(dp[j-WEI]!=-1) dp[j]=max(dp[j],dp[j-WEI]+VAL);
VAL+=val;
WEI+=wei;
c++;
}
}
}
}
ll ans=0;
f(i,s+1) ans=max(ans,dp[i]);
cout<<ans;
}
