#include <bits/stdc++.h>
#define long long long
using namespace std;
/*
优美二进制分组
nklogk
*/
const int K = 2000;
const int MIN = numeric_limits<int>::min();
int n, k;
long f[K + 1];
vector<pair<int, int>> a[K + 1];
void solve() {
cin >> k >> n;
for (int i = 0; i < n; i++) {
int v, w, c;
cin >> v >> w >> c;
a[w].push_back({v, c});
}
fill(f + 1, f + K + 1, MIN);
for (int w = 1; w < k + 1; w++) {
if (a[w].empty()) {
continue;
}
sort(a[w].begin(), a[w].end(), greater<pair<int, int>>());
// 解释一下为什么是 < k
// j 相当于已经选择了几个 w 体积的物品
int i = 0;
for (int j = 0; j * w < k; j++) {
for (int x = k; x >= w; x--) {
if (f[x - w] > MIN) {
f[x] = max(f[x], f[x - w] + a[w][i].first);
}
}
a[w][i].second = a[w][i].second - 1;
if (a[w][i].second == 0) {
i = i + 1;
}
if (i == (int) a[w].size()) {
break;
}
}
}
cout << *max_element(f, f + k + 1) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
t = 1;
for (int i = 0; i < t; i++) {
solve();
}
return 0;
}
