// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
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--){
long long newW = weight;
long long newV = val;
long long newQ = quant;
while(newQ && (j+newW)<=w){
if(dp[j+newW]<newV+dp[j]){
dp[j+newW] = newV+dp[j];
}else break;
maxQuant = max(maxQuant,dp[j+newW]);
newW+=weight;
newV +=val;
newQ--;
}
}
}
//for(int i=0;i<=w;i++) cout<<i<<" "<<dp[i]<<endl;
cout<<maxQuant<<endl;
return 0;
}
