#include <bits/stdc++.h>
using namespace std;
const int N = 2001;
int dp[N];
vector<pair<int,int>> wei[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int s,n;
cin >> s >> n;
for (int i=0; i<n; ++i){
int value,weight,nbItems;
cin >> value >> weight >> nbItems;
wei[weight].emplace_back(value,nbItems);
}
memset(dp,-1,sizeof(dp));
dp[0] = 0;
for (int w=1; w<=s; ++w){
sort(wei[w].rbegin(),wei[w].rend());
int nb = s/w;
for (auto i:wei[w]){
while (nb and i.second){
for (int k=s-w; k>=0; --k){
if (dp[k] != -1) dp[k+w] = max(dp[k+w],i.first+dp[k]);
}
i.second--;
nb--;
}
if (nb == 0) break;
}
}
int maxi = 0;
for (int i:dp) maxi = max(maxi,i);
cout << maxi;
return 0;
}
