/* (: A Lazy Coder :) */
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int s, n;
cin >> s >> n;
map<int, vector<pair<int,int>>> mp;
for(int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
mp[w].push_back({v, k});
}
vector<int> dp(s + 1, INT_MIN);
dp[0] = 0;
for(auto &[wt, vals] : mp) {
sort(vals.begin(), vals.end(), greater<>());
for(int sum = s; sum >= wt; sum--) {
int ind = 0, taken = 0, currtake = 0, profit = 0;
while(ind < vals.size() && (taken + 1) * wt <= sum) {
taken++;
currtake++;
profit += (vals[ind].first);
if(dp[sum - taken * wt] != INT_MIN) dp[sum] = max(dp[sum], dp[sum - taken * wt] + profit);
if(currtake == vals[ind].second) {
ind++;
currtake = 0;
}
}
}
}
cout << *max_element(dp.begin(), dp.end()) << "\n";
}
