#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9 + 1233445;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int s, n;
cin >> s >> n;
map<int, vector<array<int, 2>>> mp;
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
mp[w].push_back({v, k});
}
vector<array<int, 2>> items;
for (auto [w, vec] : mp) {
int sum = 0;
sort(vec.begin(), vec.end());
while (!vec.empty()) {
auto [v, k] = vec.back();
vec.pop_back();
while (k > 0 && sum + w <= s) {
sum += w;
k--;
items.push_back({w, v});
}
}
}
map<array<int, 2>, int> cnt;
for (auto [w, v] : items) {
array<int, 2> obj{w, v};
cnt[obj]++;
while (cnt[obj] == 3) {
cnt[obj] -= 2;
obj[0] *= 2;
obj[1] *= 2;
cnt[obj]++;
}
}
vector<int> knap(s + 1, -INF);
knap[0] = 0;
for (auto [obj, c] : cnt) {
auto [w, v] = obj;
while (c--) {
for (int sum = s; sum >= w; sum--) {
knap[sum] = max(knap[sum], knap[sum - w] + v);
}
}
}
cout << *max_element(knap.begin(), knap.end()) << '\n';
}
