#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> res(32);
vector<ll> solve(ll x){
res.clear();
for (ll p = 1; p <= x; p <<= 1){
res.push_back(p);
x -= p;
}
if (x > 0) res.push_back(x);
return res;
}
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;
if (b>s){continue;}
solve(c);
for (ll x : res){
ll n1 = b*x;
ll a1 = a*x;
if (n1 > s) continue; // skip impossible chunk
for (ll j = s; j >= n1; --j) {
dp[j] = max(dp[j], dp[j - n1] + a1);
}
}
}
// for (auto i : dp){
// cout << i << " ";
// }
// cout << "\n";
ll m = 0;
for (auto i : dp){
m = max(m, i);
}
cout << m;
return 0;
}
