#include <bits/stdc++.h>
using namespace std;
struct Item {
long long v , w , k;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int S , N;
cin >> S >> N;
vector<Item> a(N);
vector<vector<pair<long long , long long>>> now(S + 1);
for (int i = 0 ; i < N ; i++) {
cin >> a[i].v >> a[i].w >> a[i].k;
a[i].k = min(a[i].k , S * 1LL);
now[a[i].w].emplace_back(a[i].v , a[i].k);
}
vector<Item> b;
for (int i = 1 ; i <= S ; i++) {
sort(now[i].rbegin(), now[i].rend());
long long h = S;
for (int j = 0 ; j < (int)now[i].size() ; j++) {
long long can = min(h / i , now[i][j].second);
if (can == 0) break;
b.push_back({now[i][j].first , i , can});
h -= can * i;
}
}
auto Get_candidates = [&](long long val) {
vector<long long> c;
int po = -1;
for (int i = 11 ; i >= 0 ; i--) {
long long cur = (1LL << i);
if (cur & val) {
if (po == -1) {
po = (1 << i) - 1;
c.push_back(1);
}
else {
c.push_back(cur);
}
}
}
for (int i = 11 ; i >= 0 ; i--) {
long long cur = (1LL << i);
if (po & cur) {
c.push_back(cur);
}
}
return c;
};
int n = (int)b.size();
vector<pair<long long , long long>> who;
for (int i = 0 ; i < n ; i++) {
vector<long long> c = Get_candidates(b[i].k);
for (int j = 0 ; j < (int)c.size() ; j++) {
long long cost = b[i].w * c[j];
long long add = b[i].v * c[j];
who.emplace_back(add , cost);
}
}
vector<long long> dp(S + 1);
vector<bool> Reachable(S + 1);
Reachable[0] = true;
for (int i = 0 ; i < (int)who.size() ; i++) {
for (int j = S - who[i].second ; j >= 0 ; j--) {
if (j + who[i].second <= S && Reachable[j]) {
Reachable[who[i].second + j] = true;
dp[who[i].second + j] = max(dp[who[i].second + j] , dp[j] + who[i].first);
}
}
}
cout << *max_element(dp.begin(),dp.end()) << '\n';
return 0;
}
