#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int s, n;
cin >> s >> n;
map<int, vector<pair<int, int>>> hms;
for (int i = 0; i < n; i++) {
int v, w, a;
cin >> v;
cin >> w;
cin >> a;
if (w <= s && a > 0) hms[w].emplace_back(v, a);
}
vector<int> dp(s+1, 0);
dp[0] = 0;
// 2 4 6
// 3 5 7
for (auto& [w, vv] : hms) {
sort(vv.begin(), vv.end(), std::greater<pair<int, int>>());
for (int j = s; j >= 0; j--) {
auto amount_used = 1;
auto value_used_prev = 0;
auto it = vv.begin();
while (it != vv.end()) {
auto amount_left = it->second;
auto value = it->first;
while (amount_left > 0 && j >= w * amount_used) {
value_used_prev += value;
dp[j] = max(dp[j], dp[j - w * amount_used] + value_used_prev);
amount_left--;
amount_used++;
}
if (w * amount_used > j) {
break;
}
it++;
}
}
}
cout << dp[s];
}
