#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 = 1e6;
const int N = 2000;
long long dp[N+5];
pair<ll,ll> a[M+15];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n , k ;
cin >> k >> n ;
ll cnt = 0 ;
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[cnt]={take*x,f};
cnt++;
}
c -= take;
p <<= 1;
}
}
long long res = 0 ;
for(ll j = 0 ; j < cnt ; j++){
pair<ll,ll> x = a[j];
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 ;
}
