#include<bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(0);
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
int S, n;
cin >> S >> n;
// (w, v, k)
vector<array<int, 3>> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i][1] >> a[i][0] >> a[i][2];
}
sort(a.begin() + 1, a.end(), [](auto u, auto v) -> bool {
return u[0] == v[0] ? u[1] > v[1] : u[0] < v[0];
});
vector<array<int, 3>> b(1);
int cnt = 0, sum = 0, pre = -1;
for (int i = 1, j = 1; i <= n; i++) {
j = i;
if (a[i][0] != pre)
cnt = 0;
pre = a[i][0];
sum = 0;
while (j <= n && a[j][0] == a[i][0] && a[j][1] == a[i][1])
cnt += a[j][2], sum += a[j][2], j++;
j--;
b.push_back({a[i][0], a[i][1], min(sum, S / a[i][0])});
if (cnt < S / a[i][0]) {
i = j;
continue;
}
while (j <= n && a[j][0] == a[i][0])
j++;
i = j - 1;
}
int m = b.size() - 1;
vector<int> dp(S + 1, -2e9);
dp[0] = 0;
for (int i = 1; i <= m; i++) {
for (int k = 1; k <= b[i][2]; k++) {
for (int j = S; j >= k * b[i][0]; j--) {
dp[j] = max(dp[j], dp[j - k * b[i][0]] + b[i][1]);
}
}
}
cout << *max_element(dp.begin(), dp.end());
return 0;
}
