#include<bits/stdc++.h>
#define ll int
#define fi first
#define se second
#define pb push_back
#define endl "\n"
#define ii pair<ll,ll>
#define pi pair<ll,ll>
#define pii pair<ll, pair<ll,ll> >
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define all(s) s.begin(), s.end()
#define szz(s) int(s.size())
using namespace std;
#define ve vector<ll>
const string NAME = "file";
const int M = 998244353;
const int N = 2e5;
ll exp(ll a ,ll b){
ll res = 1LL;
while(b){
if(b&1LL)res=(res*a)%M;
b/=2 ;
a = (a*a )%M;
}
return res;
}
struct st{
ll val , w , type ;
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n , k ;
cin >> k >> n ;
vector<pair<ll,ll>>a;
for(ll i = 1 ; i <= n ; i++){
ll x , y , c ;
cin >> x >> y >> c;
if(y>k)continue;
c = min(c, k / y);
int p = 1;
while(c > 0){
if(p > k)break ;
int take = min(p, c);
long long f = take*y , ff = take*x ;
if(f > k)break ;
if(f <= k)
a.pb({take*x, f});
c -= take;
p <<= 1;
}
}
vector<long long > dp(k+5,0);
long long res = 0 ;
for(auto x : a){
REP(i,k,x.se){
dp[i] = max(dp[i] , dp[i-x.se]+x.fi);
res = max(res,dp[i]);
}
}
cout<<res<<endl;
return 0 ;
}
