#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> solve(ll x){
vector<ll> ans;
ans.push_back(1);
x-=1;
ll n = 2;
for (int i = 1; i<32; i++){
if (n<=x) {x-=n; ans.push_back(n);}
n = n*n;
}
ans.push_back(x);
return ans;
}
int main(){
iostream::sync_with_stdio(false);
cin.tie(nullptr);
int s, n;
cin >> s >> n;
vector<ll> dp(s+1, 0);
for (int i = 0; i<n; i++){
ll a, b, c;
cin >> a >> b >> c;
for (ll x : solve(c)){
ll n1 = b*x;
ll a1 = a*x;
for (ll j = s; j>=n1; j--){
if (j==n1) dp[j]=max(dp[j], a1);
if (dp[j-n1]!=0) dp[j]=max(dp[j-n1] + a1, dp[j]);
}
}
}
// for (auto i : dp){
// cout << i << " ";
// }
// cout << "\n";
ll m = 0;
for (auto i : dp){
m = max(m, i);
}
cout << m << endl;
return 0;
}
