#include<bits/stdc++.h>
using namespace std ;
long long int f(long long int i , long long int target , vector<long long int > &valnew, vector<long long int > &wtnew,vector<vector<long long int >> &dp){
if(i==0){
if(wtnew[i]<= target){
return valnew[i]*(target/wtnew[i]);
}else{
return 0 ;
}
}if(dp[i][target] != -1) return dp[i][target] ;
long long int nottake = f(i-1,target,valnew,wtnew,dp);
long long int take = INT_MIN;
if(wtnew[i] <= target){
take = f(i-1,target - wtnew[i],valnew,wtnew,dp) + valnew[i];
}
return dp[i][target] = max(take,nottake);
}
int main(){
long long int s,n;cin>>s>>n;
vector<long long int > val,wt,copy ;
for (long long int i = 0; i < n; i++)
{
for (long long int j = 0; j< 3;j++)
{
long long int x ;
cin>>x ;
if(j==0){
val.push_back(x);
}if(j==1){
wt.push_back(x);
}if(j==2){
copy.push_back(x);
}
}
}
vector<long long int > valnew,wtnew ;
for (long long int i = 0; i < n; i++)
{
for (long long int j = 0; j < copy[i]; j++)
{
valnew.push_back(val[i]);
wtnew.push_back(wt[i]);
}
}vector<vector<long long int >> dp(valnew.size(),vector<long long int >(s+1,-1));
cout<< f(valnew.size()-1,s,valnew,wtnew,dp);
}
