// https://oj.uz/problem/view/NOI18_knapsack
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int s, n;
cin >> s >> n;
vector<vector<pair<int, int>>> items_of_weight(s + 1);
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
items_of_weight[w].push_back({v, k});
}
vector<vector<int>> dp(s + 1, vector<int>(s + 1));
for (int w = 1; w <= s; w++) {
sort(items_of_weight[w].begin(), items_of_weight[w].end(), greater<pair<int, int>>());
for (int capacity = 1; capacity <= s; capacity++) {
dp[w][capacity] = max(dp[w - 1][capacity], dp[w][capacity - 1]);
int gained = 0;
int consumed = 0;
for (auto& [v, k] : items_of_weight[w]) {
if (consumed + w > capacity) {
break;
}
for (int taken = 0; consumed + w <= capacity && taken < k; taken++) {
gained += v;
consumed += w;
dp[w][capacity] = max(dp[w][capacity], gained + dp[w - 1][capacity - consumed]);
}
}
}
}
cout << dp[s][s] << '\n';
}
