#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
long long n,s;
cin>>s>>n;
vector<int>w(n),v(n),k(n);
vector<long long>values,weights;
for(int i=0;i<n;i++){
cin>>v[i]>>w[i]>>k[i];
long long sum = 0;
for(int j=0;j<32;j++){
if(sum + (1<<j) > k[i]){
values.push_back((long long)v[i]*(long long)(k[i]-sum));
weights.push_back((long long)w[i]*(long long)(k[i]-sum));
break;
}
sum += (1<<j);
values.push_back((long long)v[i]*(long long)(1<<j));
weights.push_back((long long)w[i]*(long long)(1<<j));
}
}
int ans = 0;
int m = values.size();
vector<long long>dp(s+1,0);
for(int i=m-1;i>=0;i--){
for(int j=s;j>=0;j--){
if(j >= weights[i]){
dp[j] = max(dp[j],dp[j-weights[i]] + values[i]);
}
}
}
cout<<dp[s];
}
