#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define ll long long
#define MAX_N 100005
#define MAX_W 2005
int dp[MAX_N][MAX_W];
int S, n;
void solve() {
cin >> S >> n;
map<int, vector<pair<int, int>>> items;
for (int i = 0; i < n; i++) {
int value, weight, num;
cin >> value >> weight >> num;
items[weight].push_back({value, num});
}
dp[0][0] = 0;
int i = 1;
for (auto &it : items) {
sort(it.second.begin(), it.second.end(), greater<pair<int ,int>>());
for (int w = 0; w <= S; w++) {
dp[i][w] = dp[i - 1][w];
int at = 0, k = 0, cur_k = 0, profit = 0;
while ((k + 1) * it.first <= w && at < it.second.size()) {
k++;
profit += it.second[at].first;
dp[i][w] = max(dp[i][w], dp[i - 1][w - k * it.first] + profit);
cur_k++;
if (cur_k == it.second[at].second) {
cur_k = 0;
at++;
}
}
}
i++;
}
int answer = 0;
for (int w = 0; w <= S; w++) answer = max(answer, dp[items.size()][w]);
cout << answer << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// int t; cin >> t;
while (t--) solve();
}
// 1 MB = 1000000 bytes
// 1 int = 4 bytes
// memory consumption: (sizeof(...)_int * 4) / 1000000
