#include <bits/stdc++.h>
#define vec vector
#define pp pair<int, vector<int>>
using namespace std;
int32_t main(){
ios::sync_with_stdio(0), cin.tie(0);
int s, n;
cin >> s >> n;
vec<int> prices, weight, number;
for(int i = 0; i < n; i++){
int p ,w ,n;
cin >> p >> w >> n;
prices.push_back(p);
weight.push_back(w);
number.push_back(n);
}
vec<pair<int, vec<int>>> storage; //Value, list of items
storage.reserve(s + 10);
for (int i = 0; i <= s; i++)
{
vec<int> buffs;
buffs.reserve(n);
storage.push_back(make_pair(0, buffs));
}
vec<int> toAdd;
for(int i = 0; i < n; i++){
toAdd.push_back(0);
}
storage[0].second = toAdd;
for(int i = 0; i < s; i++){
if(storage[i].second.size() != 0 || storage[i].first > 0){
for(int j = 0; j < n; j++){
if(storage[i].second[j] < number[j]){
int target = i + weight[j];
if(target <= s){
int value = storage[i].first + prices[j];
if(value > storage[target].first){
storage[target].first = value;
storage[target].second = storage[i].second;
storage[target].second[j]++;
}
}
}
}
}
}
int max = 0;
for(int i = 0; i <= s; i++){
if(max < storage[i].first)
max = storage[i].first;
}
cout << max << endl;
return 0;
}
