#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)x.size()
const int MAX = 1e5;
vector<array<ll, 2>> items_by_weight[2001];
ll dp[2001][2001]; // best V for each W using the first I weight values
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int S, N; cin >> S >> N;
int V, W; ll K;
for (int i = 0; i < N; ++i) {
cin >> V >> W >> K;
items_by_weight[W].push_back({V, K});
}
for (auto& items : items_by_weight) {
sort(items.begin(), items.end(), [](auto& item_1, auto& item_2) {
return item_1[0] > item_2[0];
});
}
for (int weight = 1; weight <= 2000; ++weight) {
auto& items = items_by_weight[weight];
vector<ll> worths = {0};
int curr_weight = 0;
for (auto& item : items) {
for (int qty = 0; qty < item[1]; ++qty) {
curr_weight += weight;
if (curr_weight > S) break;
worths.push_back(worths[sz(worths) - 1] + item[0]);
}
if (curr_weight > S) break;
}
for (int pos = S; pos >= 0; --pos) {
int increment_pos = pos;
int items_used = 0;
while (increment_pos <= S && items_used < sz(worths)) {
dp[increment_pos][weight] = max(dp[increment_pos][weight], dp[pos][weight - 1] + worths[items_used]);
increment_pos += weight;
++items_used;
}
}
}
ll ans = 0;
for (int i = 0; i <= S; ++i) {
ans = max(ans, dp[i][S]);
}
cout << ans << '\n';
}
