#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> solve(ll x){
vector<int> ans;
ll n = 1;
for (int i = 0; i<32; i++){
if (n<=x) {x-=n; ans.push_back(n);}
n = max(static_cast<ll>(2), 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;
bitset<32> num(c);
ll prev = 1;
for (auto x : solve(c)){
ll n1 = b*x;
ll a1 = a*x;
for (int 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]);
}
prev = max(static_cast<ll>(2), prev*prev);
}
}
// for (auto i : dp){
// cout << i << " ";
// }
// cout << "\n";
ll m = 0;
for (auto i : dp){
m = max(m, i);
}
cout << m << endl;
return 0;
}
