#include "bits/stdc++.h"
using namespace std;
using ll = int64_t;
#define endl '\n'
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 37
#endif
void solve() {
ll S, n;
cin >> S >> n;
map<pair<ll, ll>, ll> mp;
vector<array<ll, 3> > v(n); // val, weight, count
for(ll i = 0; i < n; ++i) {
cin >> v[i][0] >> v[i][1] >> v[i][2];
v[i][2] = min(v[i][2], S/v[i][1] + 1);
mp[{v[i][1], -v[i][0]}] += v[i][2];
}
for(auto it = mp.begin(); it != mp.end(); ++it) {
auto [w, val] = it->first;
ll cnt = it->second;
cnt = (it->second) = min(cnt, S);
if(w > S) {
break;
}
while(cnt >= 3) {
mp[{2*w, 2*val}] += cnt/3;
cnt = cnt/3 + cnt%3;
}
mp[{w, val}] = cnt;
it = mp.find({w, val});
// debug(*it);
}
const ll inf = 1e18 + 37;
vector<ll> dp(S + 1, -inf);
dp[0] = 0;
vector<int> item_cnt(S + 1);
vector<pair<ll, ll> > items(S + 1);
for(auto p : mp) {
auto [w, val] = p.first;
ll cnt = p.second;
if(w > S) {
break;
}
assert(cnt <3);
for(ll i = 0; i < cnt; ++i) {
if(item_cnt[w] < S/w + 1) {
items.push_back({-val, w});
item_cnt[w]++;
}
}
}
for(auto [item_val, item_w] : items) {
for(int W = S; W >= item_w; --W) {
dp[W] = max(dp[W], dp[W - item_w] + item_val);
}
}
// debug(items);
cout << *max_element(dp.begin(), dp.end());
}
signed main(){
#ifdef LOCAL
// freopen("test.in", "r", stdin);
freopen("err.txt", "w", stderr);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
