#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
vector<vector<ll>> process(vector<vector<pair<ll, ll>>> items, int s){
vector<vector<ll>> res(2001);
for(int i = 1; i <= 2000; i++){
int allowed = s / i;
vector<pair<ll, ll>> temp = items[i];
sort(temp.begin(), temp.end());
reverse(temp.begin(), temp.end());
if(!temp.empty()){
int idx = 0;
while(idx < temp.size() && allowed > 0){
ll curr = temp[idx].second;
ll value = temp[idx].first;
if(allowed >= curr){
allowed -= curr;
while(curr--) res[i].push_back(value);
}
else{
while(allowed--) res[i].push_back(value);
}
idx++;
}
}
}
return res;
}
int main()
{
int s, n; cin >> s >> n;
//store {v_i, k_i} in weight_i
vector<vector<pair<ll, ll>>> items(2001);
for(int i = 0; i < n; i++){
ll v, w, k; cin >> v >> w >> k;
items[w].push_back({v, k});
}
auto res = process(items, s);
vector<ll> dp(2001, 0);
for(int w = 1; w <= s; w++){
for(int val : res[w]){
for(int i = s; i >= w; i--){
dp[i] = max(dp[i], dp[i - w] + val);
}
}
}
cout << dp[s] << endl;
}
