// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,w;
cin>>w>>n;
vector<vector<int>> items(n,vector<int>(3));
vector<long long> dp(w+1,0); //Max value con peso maximo w
for(int i=0;i<n;i++) cin>>items[i][0]>>items[i][1]>>items[i][2];
long long maxQuant = 0;
for(int i=0;i<n;i++){
int weight = items[i][1];
int val = items[i][0];
int quant = items[i][2];
for(int j=w-weight;j>=0;j--){
int k = 1;
while(k<=quant && (j+weight*k)<=w){
dp[j+weight*k] = max(dp[j+weight*k],val*k+dp[j]);
maxQuant = max(maxQuant,dp[j+weight*k]);
k++;
}
}
}
//for(int i=0;i<=w;i++) cout<<i<<" "<<dp[i]<<endl;
cout<<maxQuant<<endl;
return 0;
}
