#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vpi = vector<pair<int,int>>;
using vpl = vector<pair<ll,ll>>;
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define pb push_back
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a) - 1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a) - 1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b) - 1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
struct triple{
ll x,y,z;
};
bool sorting(triple a, triple b){
if(a.y!=b.y)return a.y<b.y;
return a.x>b.x;
}
void solve(){
ll n,s; cin>>s>>n;
vector<triple>a(n);
FOR(i,n)cin>>a[i].x>>a[i].y>>a[i].z;
FOR(i,n)a[i].z=min(a[i].z,s/a[i].y);
vl dp(s+1,0);
sort(all(a),sorting);
vl cnt(s+1,0);
vector<triple>c;
FOR(i,n){
if(cnt[a[i].y]>=s/a[i].y)continue;
a[i].z=min(a[i].z,s/a[i].y-cnt[a[i].y]);
cnt[a[i].y]+=a[i].z;
c.pb(a[i]);
}
n=c.size();
FOR(i,n){
for(int x=0; (1<<x)<c[i].z; x++){
FOR_R(j,(1<<x)*c[i].y,s+1){
dp[j]=max(dp[j],dp[j-(1<<x)*c[i].y]+(1<<x)*c[i].x);
}
c[i].z-=(1<<x);
}
FOR_R(j,c[i].y*c[i].z,s+1){
dp[j]=max(dp[j],dp[j-c[i].y*c[i].z]+c[i].z*c[i].x);
}
}
ll ans=0;
FOR(i,s+1)ans=max(ans,dp[i]);
cout<<ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
