#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define mp make_pair
#define F first
#define S second
constexpr int maxn = 100005;
constexpr int maxs = 2005;
int n, s;
vector<pii> items_list[maxs]; // items[w] = [all pairs (v, k) with value w]
vector<pii> items; // items = list of (value,weight), sorted, at most s/w items per w
int knapsack() {
int N = items.size();
vector<vector<int>> K(N + 1, vector<int>(s + 1));
// Build table K[][] in bottom up manner
for (int i = 0; i <= N; i++) {
for (int w = 0; w <= s; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (items[i - 1].S <= w)
K[i][w] = max(items[i - 1].F + K[i - 1][w - items[i - 1].S], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[N][s];
}
int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
cin >> s >> n;
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
items_list[w].pb(mp(v, k));
}
for (int i = 1; i <= s; i++) {
// sort by value
sort(items_list[i].begin(), items_list[i].end(), greater<pii>());
// add items to items
int counter = 0;
for (pii item_type : items_list[i]) {
for (int j = 0; j < item_type.S; j++) {
items.push_back(mp(item_type.F, i));
counter++;
if (counter == s / i) break;
}
}
}
// for (pii item : items) {
// cout << "value: " << item.F << '\t' << "weight: " << item.S << '\n';
// }
cout << knapsack() << '\n';
return 0;
}
