#include<bits/stdc++.h>
using namespace std ;
int f(int i , int target , vector<int> &valnew, vector<int> &wtnew,vector<vector<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] ;
int nottake = f(i-1,target,valnew,wtnew,dp);
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(){
int s,n;cin>>s>>n;
vector<int> val,wt,copy ;
for (int i = 0; i < n; i++)
{
for (int j = 0; j< 3;j++)
{
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<int> valnew,wtnew ;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < copy[i]; j++)
{
valnew.push_back(val[i]);
wtnew.push_back(wt[i]);
}
}vector<vector<int>> dp(valnew.size(),vector<int>(s+1,-1));
cout<< f(valnew.size()-1,s,valnew,wtnew,dp);
}
