#include <bits/stdc++.h>
using namespace std;
struct item {
int value;
int weight;
int amount;
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int S,N;
cin >> S >> N;
vector<item> itemTypes(N+1,item());
int totalItems=0;
for(int i=0;i<N;i++){
cin >> itemTypes[i].value >> itemTypes[i].weight >> itemTypes[i].amount;
totalItems+=itemTypes[i].amount;
}
vector<int> dp(S+1,0); //max value for [i(this weight)][j(how many used)]
vector<int> dpAfter(S+1,0); //max value for [i(this weight)][j(how many used)]
int currentItemIndex = 0;
item currentItem = itemTypes[currentItemIndex];
int count=0;
int maxValue=0;
// cout << "GO\n";
for(int item=0;item<totalItems;item++){
// cout << "dping on "<<currentItemIndex<<endl;
for(int i=0;i<S;i++){
// dp[i]=max(dp[i],dp[i]);
if(i+currentItem.weight<=S){
// cout << "i"<<i<<"+weight("<<currentItem.weight<<") <= "<<S<<endl;
dpAfter[i+currentItem.weight]=max(dpAfter[i+currentItem.weight],dp[i]+currentItem.value);
maxValue=max(maxValue,dpAfter[i+currentItem.weight]);
}
// cout << "i is now "<<i<<endl;
}
for(int i=0;i<S+1;i++){
dp[i]=dpAfter[i];
}
// fill(dpAfter.begin(),dpAfter.end(),0);
count++;
if(count==currentItem.amount){
count=0;
currentItemIndex++;
currentItem = itemTypes[currentItemIndex];
}
}
cout << maxValue << "\n";
}
