#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__)
void solve(){
ll n,s; cin>>s>>n;
ll a[n][3];
FOR(i,n)cin>>a[i][0]>>a[i][1]>>a[i][2];
FOR(i,n)a[i][2]=min(a[i][2],s/a[i][1]);
vl dp(s+1,0);
FOR(i,n){
for(int x=0; (1<<x)<a[i][2]; x++){
FOR_R(j,(1<<x)*a[i][1],s+1){
dp[j]=max(dp[j],dp[j-(1<<x)*a[i][1]]+(1<<x)*a[i][0]);
}
a[i][2]-=(1<<x);
}
FOR_R(j,a[i][2]*a[i][1],s+1){
dp[j]=max(dp[j],dp[j-a[i][2]*a[i][1]]+a[i][2]*a[i][0]);
}
}
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;
}
