#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;
int p = 1;
while(c > 0){
int take = min(p, c);
if(take * y <= k)
a.pb({take*x, take*y});
c -= take;
p <<= 1;
}
}
ve dp(k+5,0);
for(auto x : a){
REP(i,k,0){
if(i-x.se >= 0 ){
dp[i] = max(dp[i] , dp[i-x.se]+x.fi);
}
}
}
ll res = 0 ;
FOR(i,0,k){
res =max(res,dp[i]);
// cout<<i<< " "<<dp[i]<<endl;
}
cout<<res<<endl;
// for(auto x : a)cout<<x.fi<<" "<<x.se<<endl;
return 0 ;
}
