#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[2001][2001];
ll inf = 2e18+5;
int main() {
int S, N; cin >> S >> N;
map<int, vector<pair<int, int>>> weight_groups;
for(int i = 0, v, w, k; i < N; ++i) {
cin >> v >> w >> k;
weight_groups[w].push_back({v, k});
}
for(int i = 0; i <= 2000; ++i) {
for(int j = 0; j <= 2000; ++j) {
dp[i][j] = -inf;
}
}
dp[0][0] = 0;
int cur_item = 0;
for(auto &[weight, group] : weight_groups) {
cur_item++;
sort(group.begin(), group.end(), greater<pair<int, int>>());
for(int i = 0; i <= S; ++i) {
int take = 0;
int groups_taken = 0;
int local_at = 0;
ll value = 0;
dp[cur_item][i] = dp[cur_item-1][i];
while(weight * (take + 1) <= i && groups_taken < (int)group.size()) {
take++;
value += group[groups_taken].first;
dp[cur_item][i] = max(
dp[cur_item][i],
dp[cur_item-1][i - weight * take] + value
);
local_at++;
if(local_at == group[groups_taken].second) {
local_at = 0;
groups_taken++;
}
}
}
}
ll mx = 0;
for(int i = 0; i <= S; ++i) mx = max(mx, dp[cur_item][i]);
cout << mx << "\n";
}
