#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Item
{
int v, w, k;
};
int s, n;
Item store[100'000];
ll dp[2001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> s >> n;
for (int i = 0; i < n; ++i) {
cin >> store[i].v >> store[i].w >> store[i].k;
}
sort(store, store + n, [](Item &a, Item &b) {
if (a.w != b.w) return a.w < b.w;
return a.v > b.v;
});
vector<pair<int, int>> store_simplified;
int current_weight = store[0].w;
int accumulated_freq = 0;
for (int i = 0; i < n; ++i) {
if (current_weight != store[i].w) {
current_weight = store[i].w;
accumulated_freq = 0;
}
int given = min({2000 / current_weight, 2000 - accumulated_freq, store[i].k});
if (given > 0) {
for (int j = 0; j < given; ++j) {
store_simplified.push_back({store[i].v, current_weight});
}
}
accumulated_freq += given;
}
n = store_simplified.size();
for (int i = 0; i < n; ++i) {
for (int w = s; w >= 0; --w) {
if (w - store_simplified[i].second >= 0) {
dp[w] = max(dp[w], dp[w - store_simplified[i].second] + store_simplified[i].first);
}
}
}
cout << dp[s] << '\n';
return 0;
}
