/*
* Author: bubu2006
**/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll limit, n;
cin >> limit >> n;
// since limit <= 1000 and W[i] <= limit -> we can group items by weight
map<int, vector<pair<int, int>>> weight;
for(int i = 0; i < n; i++) {
int val, w, cnt;
cin >> val >> w >> cnt;
if(w <= limit && cnt >= 1) {
weight[w].push_back({val, cnt});
}
}
int sz = weight.size();
vector<vector<ll>> dp(sz + 1, vector<ll>(limit + 1, INT_MIN));
dp[0][0] = 0;
int index = 1;
for(auto& [w, items] : weight) {
// sort items by value
sort(items.rbegin(), items.rend());
for(int curlimit = 0; curlimit <= limit; curlimit++) {
// if can reach sum with s using index - 1 then can reach with index
dp[index][curlimit] = dp[index - 1][curlimit];
int copies = 0; // the current number of copies with weight "w"
int curtype = 0; // current type we are considering
int curused = 0; // count the number of used item of curtype
ll profit = 0; // the current profit
while((copies + 1) * w <= curlimit && curtype < (int)items.size()) {
copies++;
profit += items[curtype].first;
if(dp[index - 1][curlimit - copies * w] != INT_MIN) {
dp[index][curlimit] = max(dp[index][curlimit], dp[index - 1][curlimit - copies * w] + profit);
}
curused++;
if(curused == items[curtype].second) { // used all items of this value
curtype++; // move to the next type
curused = 0;
}
}
}
index++;
}
cout << *max_element(dp.back().begin(), dp.back().end()) << '\n';
}
