#include <bits/stdc++.h>
#define maxw 2005
using namespace std;
vector<pair<int,int>> items[maxw];
vector<pair<int,int>> filtered;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int s,n;
cin >> s >> n;
for(int i = 0;i < n;i++){
int v,w,k;
cin >> v >> w >> k;
items[w].push_back({v,k});
}
for(int i = 1;i <= s;i++){
if(items[i].empty()) continue;
int maxItems = s/i;
sort(items[i].rbegin(),items[i].rend());
for(auto item: items[i]){
if(maxItems == 0) break;
int change = min(item.second,maxItems);
maxItems -= change;
for(int j = 0;j < change;j++){
filtered.push_back({item.first,i});
}
}
}
int dp[s+1]{0};
for(auto item: filtered){
for(int i = s;i >= item.second;i--){
dp[i] = max(dp[i],dp[i-item.second] + item.first);
}
}
cout << dp[s];
return 0;
}
